2.2 Eigenvalues and eigencolumns

Definition 2.2.1   Let $M$ be a $n\times n$ square matrix. A column $V\in\mathbb{C}^{n}$ is an eigencolumn of matrix $M$ when (1) column $V$ is not null and (2) there exist a constant $\lambda\in\mathbb{C}$ (the associated eigenvalue) such that :

$$M . V=\lambda V$$

Theorem 2.2.2   A constant $\lambda$ is an eigenvalue of the square matrix $M$ if and only if $\lambda$ is a root of the characteristic polynomial:

$$\chi_{M}\left(\lambda\right)\doteq\det\left(\lambda-M\right)=\lambda^{n}-\mathrm{trace} M \lambda^{n-1}+\cdots+\left(-1\right)^{n} \det M$$

Proof. When $\lambda$ is an eigenvalue, $\left(\lambda-M\right) . V=\overrightarrow{0}$ where $V\neq\overrightarrow{0}$. Thus matrix $\left(\lambda-M\right)$ cannot be inverted and its determinant must vanish. When $\det A=0$ the map $V\mapsto A . V$ is not injective and its kernel is strictly greater than the nullspace. Applied to $A=\lambda-M$, this gives an eigencolumn. $\qedsymbol$

Remark 2.2.3   Formulas $\det \left( \begin{smallmatrix}a & b c & d \end{smallmatrix} \right) =a d-b c$ and :

$$\det\left(\begin{array}{ccc} a & b & c\\ d & e & f\\ g & h & j\end{array}\right)=aej+bfg+cdh-afh-bdj-ceg$$

(the Sarrus rule) are well known. More generally, $\det M$ is the sum of $n!$ terms, each of them being the product of $n$ factors (one per row, one per column) with the appropriate signs.

Obviously, a determinant is not computed as the sum of this horrible number of terms. With efficient algorithms, the complexity is around $n^{3}$.

Definition 2.2.4   A $n$-sized square matrix is diagonalizable when one can find $n$ linearly independent eigencolumns. In other words, this happens when one can find an invertible matrix $P$ and a diagonal matrix $\Delta$ such that :

$$P^{-1} M P=\Delta\quad;\quad M=P \Delta P^{-1}$$

Proposition 2.2.5   When $Q$ is invertible, then $M$ and $Q^{-1} . M . Q$ share the same characteristic polynomial. And therefore share the same trace (opposed to the sum of roots) and the same determinant (the product of roots or its opposite)

Theorem 2.2.6   When the characteristic polynomial has no repeated roots, the matrix is ever diagonalizable.

Proof. For each eigenvalue $\lambda_{i}$, it exists at least one eigencolumn $V_{i}\neq\vec{0}$. What is to be proved is that $\sum\mu_{i}V_{i}=\vec{0}$ implies $\forall i : \mu_{i}=0$. The Vandermonde trick is as follows. For all $j\in\mathbb{N}$, we have

$$\vec{0}=M^{j} . \vec{0}=M^{j} . \sum\mu_{i}V_{i}=\sum\left(\lambda_{i}^{j}\right)$$

Stacking the $n$ equations obtained when $j$ ranges from 0 to $n-1$, we obtain that Vandermonde matrix times matrix $\left[\mu_{1}V_{1}, \cdots, \mu_{n}V_{n}\right]$ is the null matrix. But the determinant of the Vandermonde matrix is $\prod_{j>k}\left(\lambda_{j}-\lambda_{k}\right)$. Therefore each $\mu_{i}V_{i}$ vanishes and this enforces $\forall i : \mu_{i}=0$. $\qedsymbol$

Theorem 2.2.7   A real symmetric matrix is always diagonalizable, its eigenvalues are real and $P$ can be taken orthogonal real (i.e. such that $\raisebox{0.5 em}{\normalfont\textsf{t}}{P} . P$ is diagonal).

Proof. Let $S$ be real symmetric, $V$ an eigencolumn and $\lambda\in\mathbb{C}$ the corresponding eigenvalue. Quantity $\raisebox{0.5 em}{\normalfont\textsf{t}}{\overline{V}} S V$ is a number, and thus invariant by transposition. Therefore :

$$\begin{array}{clllc} \lambda \left\vert V\right\vert^{2} & ... ...) & =\overline{\lambda} \left\vert V\right\vert^{2}\end{array}$$

and $\lambda$ is real. Then $\Re V$ and $\Im V$ are either eigen- or null vectors (for the same $\lambda$), so that $V$ real can be assumed. An orthogonal basis can ever be found for each eigenspace. For a less cursive proof, the reader is referred to Arnaudiès and Fraysse (1990, p.110). $\qedsymbol$