Algoritmus pro inverzi nad Zp
Úloha číslo: 2588
Je správně následující návod?
Dotaz: "Zajímalo by mě, jak lze v Matlabu počítat v konečných tělesech.
Například, lze nějakým pěkným způsobem násobit nebo invertovat matice, jejichž koeficienty jsou z konečného tělesa, řekněme z tělesa zbytkových tříd modulo prvočíslo?"
Odpověď: "Kdysi jsem to potřeboval. Násobení není žádný problém. Vypočítej normální součin a výsledek vem modulo prvočíslo. To se snadno dokáže. Myslím, že jsem zkoušel podobný postup pro inverzi. Algoritmus (jestli se správně pamatuju) vypadal takto:
1. Spočítej inverzi;
2. Vynásob inverzi determinantem původní matice;
3. Výsledek přepočítej modulo prvočíslo.
Přišel jsem na tento algoritmus intuicí a nikdy jsem ho nezkusil dokázat, ale fungoval skvěle."
Řešení
V druhém kroku je vypočtena \(\det(\mathbf A)\mathbf A^{-1}\), tedy adjungovaná matice nad \(\mathbb R\).
Faktorizací podle \(p\) se ve třetím kroku získá adjungovaná matice nad \(\mathbb Z_p\).
V případě, že \(\det(\mathbf A)\ne 1\), v našem případě \(\det(\mathbf A)\not\equiv 1 \pmod p\), jsou inverzní a adjungovaná matice různé.
Abychom dostali inverzní matici nad \(\mathbb Z_p\) je třeba adjungovanou matici ještě vydělit determinantem.
Algoritmus mohl fungovat skvěle leda tak nad \(\mathbb Z_2\)
