Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 6

For $u=(1,1,1{)}^T$, the all-ones matrix is $A=u{u}^T$, so $Au=3u$ and $Av=0$ whenever $v_1+v_2+v_3=0$. These subspaces have dimensions one and two and span ${\mathbb{R}}^3$. Thus the eigenvalues are $3$ and $0$.

The eigenspace for 3 has basis $\{(1,1,1{)}^T\}$. The eigenspace for 0 is the plane $v_1+v_2+v_3=0$, with basisThe last two vectors are linearly independent and every vector in the plane equals $v_1(1,0,-1{)}^T+v_2(0,1,-1{)}^T$.

Assume $n\ge 1$. With $u=(1,\dots ,1{)}^T$, the all-ones matrix satisfies $Av=({\sum }_j{v}_j)u$. Hence $n$ is an eigenvalue, and for $n\ge 2$ the other eigenvalue is $0$. At $n=1$ the matrix is $[1]$, so 1 is its only eigenvalue; zero is not an eigenvalue with a nonzero eigenvector in that case.

A basis of $E_n$ is $\{u\}$. For $n\ge 2$,The displayed vectors are linearly independent by their first $n-1$ coordinates, and every vector with zero coordinate sum has exactly that expansion. At $n=1$ this list is empty and the kernel is $\{0\}$; it is not an additional eigenspace associated with a present eigenvalue. This is the spectrum of an all-ones matrix.

The decomposition into $\mathrm{span}\{u\}$ and the zero-sum vector subspace gives characteristic polynomial $t^{n-1}(t-n)$. For $n\ge 2$, $n$ has algebraic multiplicity and geometric multiplicity one; zero has both multiplicities $n-1$. At $n=1$, only the eigenvalue 1 occurs, with both multiplicities one. Referring to a multiplicity zero for the absent root zero is merely a bookkeeping convention, not an assertion that it is an eigenvalue.

The all-ones matrix is diagonalizable for every $n\ge 1$. The vector $u$ together with the $n-1$ vectors from part (ii) is an eigenbasis. Independence follows because a multiple of $u$ has coordinate sum $n$ times that multiple, whereas every other basis vector has coordinate sum zero. In this basis the diagonal matrix is $\mathrm{diag}(n,0,\dots ,0)$. At $n=1$ the one-vector basis suffices. Alternatively, the spectral theorem for real symmetric matrices applies. If dimension zero is allowed by the convention for $\mathbb{N}$, the empty $0\times 0$ matrix has no eigenvalues, an empty basis and a vacuous diagonalization.

If $B^k=0$ with $k\ge 1$, put $S=I+B+\cdots +B^{k-1}$. The matrix geometric series telescopes on both sides:Thus $I-B$ is nonsingular, andThis is a finite polynomial identity for a nilpotent matrix; no convergence argument or bound $\Vert B\Vert <1$ is required.

Write $B=QD{Q}^{-1}$ with $D$ a diagonal matrix. Then $0=B^k=Q{D}^k{Q}^{-1}$, so each diagonal entry ${\lambda }_i$ satisfies ${\lambda }_i^k=0$ and therefore ${\lambda }_i=0$. Hence $D=0$ and $B=0$. Conversely the zero matrix is diagonalizable and nilpotent. This proves the existing result that a diagonalizable nilpotent matrix is zero; nilpotence alone does not imply a zero matrix, because nonzero nilpotent Jordan blocks exist.