Algorithmus zur Quadratwurzel einer Matrix

Question

Annehmen $A = A^T$ und nehme an, die Einträge von $A$ sind in $\mathbb{Z}^+$. Ich möchte alle Matrizen finden$M$ mit natürlichen Einträgen, so dass: $$M^2 = A$$Wie kann man das machen? Ich kenne Techniken, die eine Quadratwurzel einer beliebigen Matrix erhalten, aber ich möchte den vollständigen Satz. Ich möchte dies für große Matrizen effizient tun können ~$100 \times 100$.

Natürlich muss die Menge endlich sein, da wir über positive ganze Zahlen und die Matrix arbeiten $A$ gibt Obergrenzen.

Answer 1

Finden Sie eine invertierbare Matrix $B$ und diagonale Matrix $D$ so dass $D=B^{-1}AB$. Dann nimm alle Quadratwurzeln$D_1,...,D_m$ (alle diagonal gibt es $m\le 2^n$ davon wo $n$ ist die Größe von $A$ weil jede nicht negative Zahl höchstens 2 Quadratwurzeln hat) von $D$ und alle Matrizen $BD_iB^{-1}$. Schauen Sie, welche dieser Matrizen über natürlichen Zahlen liegen.

Answer 2

In gewisser Weise folgt, wenn Sie eine generieren können, der Rest, da, wenn Sie eine Lösung haben, eine andere Matrix $M'$ müssen die folgenden Gleichungen einhalten: $$(M-M')(M+M')=M^2-M'^2 =0 $$ Nun, nach der Definition von $M,\;M'$Sie sind gleichzeitig orthogonal diagonalisierbar, daher können Sie davon ausgehen, dass WLOG diagonal ist. Noch mehr kennen Sie die Eigenwerte von$M,\;M'$ sutisfy $\mu_i^2=\mu'^2_i = \lambda_i\to \mu_i=\mu'_i$ (Dies sind jeweils die Eigenwerte von $M,\;M'$ und $\lambda$ ist von $A$). Daher ist es gleichbedeutend mit der Bedingung, eine andere Matrix zu erhalten, die Ihre Frage beantwortet$$(\mu_i+\mu_i')\cdot(\mu_i-\mu_i')=0$$Für alle Eigenwerte. Dies ergibt eine vollständige Klassifizierung der Lösungen.