Vollständiger Graph/Adjazenzmatrix/l-te Potenz/Aufgabe/Kommentar

Zu bestimmen ist die Matrixpotenz ${}A^{\ell }$, wobei

$A={\begin{pmatrix}0&1&\ldots &1&1\\1&0&1&\ldots &1\\\vdots &\ddots &\ddots &\ddots &\vdots \\1&\ldots &1&0&1\\1&1&\ldots &1&0\end{pmatrix}}$

die Adjazenzmatrix des vollständigen Graphen ${}K_{n}$ ist. Um eine (große) Potenz einer Matrix zu berechnen, besteht die erste Idee darin, die Matrix in eine Diagonalmatrix umzuwandeln. In Beispiel wurden die Eigenwerte und Eigenvektoren von ${}A$ schon berechnet. Aus der linearen Algebra weiß man, dass ${}A$ diagonalisierbar ist und es gilt

$B^{-1}AB={\begin{pmatrix}-1&0&\ldots &0&0\\0&-1&0&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&-1&0\\0&0&\ldots &0&n-1\end{pmatrix}},$

wobei

$B={\begin{pmatrix}1&0&\ldots &0&1\\-1&1&0&\ldots &1\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &-1&1&1\\0&0&\ldots &-1&1\end{pmatrix}}$

die Matrix ist, deren Spalten aus Eigenvektoren von ${}A$ bestehen. Es ist

$B^{-1}A^{\ell }B=(B^{-1}AB)^{\ell }={\begin{pmatrix}(-1)^{\ell }&0&\ldots &0&0\\0&(-1)^{\ell }&0&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&(-1)^{\ell }&0\\0&0&\ldots &0&(n-1)^{\ell }\end{pmatrix}}.$

Somit gilt

$A^{\ell }=B{\begin{pmatrix}(-1)^{\ell }&0&\ldots &0&0\\0&(-1)^{\ell }&0&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&(-1)^{\ell }&0\\0&0&\ldots &0&(n-1)^{\ell }\end{pmatrix}}B^{-1}.$

Es bleibt also, die inverse Matrix ${}B^{-1}$ zu bestimmen. Dies kann man beispielsweise mit Fakt

durchführen.

Zur kommentierten Aufgabe