2
$\begingroup$

In document describing Friendship theorem, I found:

$n=k^2-k+1$

...

the matrix $A^2$ has $k$ on the diagonal and $1$ everywhere else. We can write:

$A^2=J+(k-1)I$

(Note: $J$ is matrix whose entries are all $1$ and $I$ is identity matrix, all matrix square $n\times n$)

From this expression, it's easy to see that $A^2$ has eigenvalues $n+k-1=k^2$, and $k-1$ of multiplicity $n-1$.

How those eigenvalues are calculated ?

Source document: http://math.mit.edu/~fox/MAT307-lecture20.pdf

2 Answers 2

1

Recall that if the sum of each row is some constant number $s$ then $s$ is an eigenvalue.

Here you have it that each row have $n-1$ ones and one $k$ (where the $k$ is on the diagonal) so $n-1+k$ is an eigenvalue.

Regarding $k-1$: simply reduce $(k-1)I$ from the diagonal to find that you get the matrix $J$ (all entries are $1$), so clearly the dimension spanned by the rows is $1$ which gives that the eigenspace of the eigenvalue $k-1$ is of dimension $n-1$.

Note: This gives the geometric multiplicity but since $A^{2}$ is symmetric this is the same as the algebraic multiplicity (because $A^{2}$ is diagonalizable).

ADDED: If $k$ is real (and I believe in your case it is) then note those eigenvalues are different since there is no real solution for the equation $k-1=k^2-k+1$ so we found to eigenvalues and one with geometric multiplicity at least $1$ and the other with geometric multiplicity $n-1$ hence the geometric multiplicity of the first eigenvalue is $1$ and we have it that there are $n$ independent eigenvectors so $A^2$ is diagonalizable wich means that algebraic multiplicity = geometric multiplicity

  • 0
    No need for a source. take $v=(1,...,1)$ and check that it is an eigenvector with an eigenvalue $s$2012-10-19
1

Subtracting $k-1$ on the diagonal leads to $J$. All vectors orthogonal to the vector with all entries $1$ are annihilated by $J$. The space of vectors in an $n$-dimensional space orthogonal to a given vector is $(n-1)$-dimensional. Thus the eigenspace of the eigenvalue $k-1$ is $(n-1)$-dimensional, and since $A^2$ is symmetric, this is also the algebraic multiplicity of the eigenvalue. That leaves only a one-dimensional subspace as the eigenspace of the remaining eigenvalue, and since $A^2$ is symmetric this must be orthogonal to the eigenspace for $k-1$, so it must be the space spanned by the vector with all entries $1$; applying $A^2$ to that vector yields the corresponding eigenvalue $n+k-1$.

  • 0
    Thanks, this solutions sounds difficult for me, but I will investigate further. Now I will find more about constant sum of a row in other response. Plus for you.2012-10-19