[MD-sorular] idempotent

[zati lokum]

2. yazdığınız yol baya uzun sürer, çünkü tek tek ters arıyorsunuz. Grup
sonlu ise ve birim varsa elemanı kendisiyle çarpıp ne zaman birime eşit
olduğunu bulmak daha kolay (efficient) sanırım. Grup hele de çok büyükse, en
azından elemanın orderı grubun orderını böler, yani daha küçüktür. Daha iyi
yöntem olabilir. Çok güzel soruymuş.

Zati

2010/7/24 Metin Odun <metamaths at gmail.com>

> Sizin dediğiniz 4 kümeye ayırma işlemi için şöyle bir algortma düşündüm.
>
> 1- Bir grupta biricik idempotent olduğundan, her elemanı kendisiyle çarpıp
> kendisine eşit mi diye bakarız. Böylece birimi tespit ederiz.
> 2- Artık elimizde birim eleman olduğundan, her elemanı kendisiyle çarpıp
> birime eşit mi diye bakarız, eşit olanların tersleri kendileridir. Ve geriye
> kalan elemanlar da tersleri kendisine eşit olmayanlardır. Geriye tek sayıda
> eleman kalırsa ilk verilen elemanların grup oluşturmadığı anlaşılır. Ama
> tersi kendisi olmayanları iki kümeye bölmek için (kendileri ve tersleri diye
> iki küme) iyi bir yol bulamadım. Bunun için, mesela bir elemanı alıp tek tek
> diğerleriyle çarparız, birimi bulursak eldeki elemanın da tersini bulmuş
> oluruz.
>
> Metin
>
> 24 Temmuz 2010 12:10 tarihinde Metin Odun <metamaths at gmail.com> yazdı:
>
>> m + n^2 -n + 2nm <= (1+n+2m)^2. olacak.
>>
>> 24 Temmuz 2010 12:09 tarihinde Metin Odun <metamaths at gmail.com> yazdı:
>>
>>  Teşekkürler. Bu biraz geliştirilebilir belki ama keyfi bir grup için pek
>>> sanmıyorum. Sonuçta bu bulduğunuz bir upper bound, yani 2m^2 -m + n^2 -n +
>>> 2nm <= (1+m+2m)^2. Ve daha iyi boundlar olabilir, en azından bazı gruplar
>>> için bu soru çok zor olabilir. Açıkçası internette aradım ama bulamadım.
>>>
>>> Go:kh at n Zeytin'in bir mesajı var: "Bir küme ve o küme üzerinde ikili
>>> işlem tanımı gereği kapalılığı göstermeye gerek yoktur. Çünkü o küme
>>> üzerindeki işlemde birleşme, etkisiz eleman, ters eleman özelliği bilinirken
>>> grup için yeterli şartlar sağlanmış olur. A boştan farklı küme olmak üzere
>>>
>>> * : AxA -) A   ikili işlem tanımlı olduğundan kapalılık göstermeye gerek
>>> yok. Küme üzerinde ikili işlem tanımlı olduğunu bilmek yeterli."
>>>
>>> Bu arada Ali Nesin'in bir evvelki matematiksel soruma verdiği tek
>>> cümlelik yanıtı daha iyi anladım. O cümle trivial caseleri ekarte edip
>>> herşeyi ortaya koyuyordu, üzerine mesaj yazmam gereksizdi. Derin bir
>>> cümleydi.
>>>
>>> 24 Temmuz 2010 00:35 tarihinde Ezgi Kantarcı <ezzzgi at gmail.com> yazdı:
>>>
>>> Merhaba,
>>>>
>>>> Birleşmelilik ve ters elemanların verdiği avantaj, mesela tersi -
>>>> olarak düşünürsek, a,-a,b,-b dört elemansa diyelim,
>>>> normalde a+b, a-b, -a+b, -a+b, b+a, b-a,-b+a,-b-a'yı kontrol
>>>> edeceksek, onun yerine a+b, a-b, b+a, b-a'yı kontol etmemizin yeterli
>>>> olması.
>>>>
>>>> grubu ayrık dört parçaya ayırdık diyelim: 0 (etkisiz eleman), tersi
>>>> kendisi olan 0 dışındaki elemanlar, "bazı elemanlar", onların tersleri
>>>> olarak.
>>>> diyelim ki bu grupların eleman sayıları sırayla 1,n,m ve m. O zaman
>>>> "bazı elemanlar" arasından a,b ikilileri seçip onlar için a+b, a-b,
>>>> b+a, b-a 'ya bakarız. Bu 4 m (m-1)/2 işlem. Sonra "bazı elemanlar"daki
>>>> her a elemanı için a+a 'ya bakarız. Bu m işlem verir. Tersi kendisi
>>>> olan elemanlardan a,b ikilileri seçeriz ve onlar için a+b ve b+a'ya
>>>> bakarız. Bu 2 n (n-1)/2 işlem verir. Son olarak da
>>>> "bazı elemanlar"dan a elemanları, tersi kendisi olanlardan b
>>>> elemanları için a+b ve b+a 'ya bakarız. Bu da 2n*m işlem verir.
>>>> Toplam 2m^2 -m + n^2 -n + 2nm işlem oluyor.
>>>>
>>>> Örneğin 20 elemanlık grupta  0 dışında tersi kendisi olan tek eleman
>>>> varsa n=1, m=9 oluyor. 171 adım.
>>>>
>>>> Yani çok takip edilebilir oldu mu emin değilim, işlem sayısını
>>>> azaltmak için aklıma gelen bu şu anda.
>>>>
>>>> Ezgi
>>>>
>>>>
>>>> 2010/7/23 Metin Odun <metamaths at gmail.com>:
>>>>  > Bir küme ve o küme üzerinde bir işlemin birleşmeliliği, etkisiz
>>>> eleman
>>>> > özelliği ve ters eleman özelliğini sağladığı bilinirken kapalılığı
>>>> > sağladığını göstermenin pratik bir yolu var mı?
>>>> > Sadece kapalılık olsaydı soru zordu ama birleşmelilik ve ters eleman
>>>> > özellikleri bazen adımları kısaltıyor. Belki bununla ilgili güzel bir
>>>> örnek
>>>> > bilen vardır. Mesela 20 tane eleman vardır. Normalde tabloda 400
>>>> eleman var.
>>>> > Ama belki mesela 100 küsur adımda kapalılığı gösterebiliriz...
>>>> > Asıl soru w^3=1 olmak üzere w kullanarak (Yani sanırım "Dihedral grup
>>>> olarak
>>>> > kompleks matris temsili" deniyor.) S_3'e izomorf olduğu iddia edilen
>>>> bir
>>>> > grupla ilgiliydi. Orada w, w^2 ve w^3 kullanılarak 6 tane eleman
>>>> verilmiş
>>>> > matris olarak. Bunun 6 elemanlı grup olduğunu göstermekti soru.
>>>> Kapalılığı
>>>> > tek tek tüm elemanları bularak gösterdim, bir-iki yerde işlem kısaldı
>>>> ama bu
>>>> > yol genelde uzun.
>>>> > Yukarıdaki soru oradan aklıma geldi.
>>>> > _______________________________________________
>>>> > MD-sorular e-posta listesi
>>>> > sorular at matematikdunyasi.org
>>>> > http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
>>>> >
>>>>
>>>
>>>
>>
>
> _______________________________________________
> MD-sorular e-posta listesi
> sorular at matematikdunyasi.org
> http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
>
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20100724/7d28cebe/attachment.htm>