# Number of Eigenvectors in a Symmetric Matrix

Supposing symmetric matrix $A_{n\times n}$, how do I know that there are $n$ eigenvectors of $A$?

By way of trying to communicate context, I've spent a rather unproductive 5 or so hours watching various YouTube videos on the spectral theorem, orthogonal diagonalization, algebraic-bounding-geometric multiplicity, and thumbing through Anton's Elementary Linear Algebra (4.6 Change of Basis, 5.1 Eigenvalues and Eigenvectors, 5.2 Diagonalization, 6.4 Gram-Schmidt Process, 7.1 Orthogonalization, 7.2 Orthogonal Diagonalization, and 9.4 Singular Value Decomposition). (This video I found the most helpful, but didn't quite understand why $A$ defines an $(n - 1)\times (n - 1)$ matrix)

I'm sure the answer to my question is in there somewhere, but something isn't quite clicking.

I understand:

• that $A = A^T$, and alternatively-stated that $\langle A\vec{x},\vec{y} \rangle = \langle \vec{x},A\vec{y}\rangle$.
• that, if $\vec{x}$ and $\vec{y}$ are eigenvectors of $A$, and if $\lambda \neq \mu$, then $\lambda\langle \vec{x},\vec{y} \rangle = \langle \lambda\vec{x},\vec{y} \rangle = \langle A\vec{x},\vec{y} \rangle = \langle \vec{x},A\vec{y}\rangle = \langle \vec{x},\mu\vec{y}\rangle = \mu\langle \vec{x},\vec{y}\rangle = 0$
• I don't understand how I know there's a next eigenvector of $A$, or how I would know that $\lambda \neq \mu$.
• that, from the fundamental theorem of algebra, every square matrix must have at least one eigenvector (since $det(\lambda I - A) = 0$ must have at least one solution.
• that I can iteratively generate, through the Gram-Schmidt process, an orthonormal basis given a set $B$ that forms a basis. That is, if I know that I have $n$ eigenvectors, I know through G-S that I can generate an orthonormal basis for the eigenspace wherever I have repeated roots.

I don't yet know what Hermitian, unitary, and conjugate transpose mean.

I also don't understand how I know that there exists a symmetric matrix of size $(n-1)\times (n-1)$, such that I would simply be able to presume that another eigenvector has to exist in or come out of that iteratively-smaller matrix.

• Since $A$ is symmetric you know it is diagonizable. Hence if you consider $A \in \mathcal{M}(\mathbb{R}^{n \times n})$ then due to its diagonizability it has $n$ eigenvalues. The same (but more naturally) will hold if $A$ has entries over $\mathbb{C}$. – Tolaso Jul 5 '16 at 4:46
• As for Hermitian matrices you may take a look here and for unitary matrices here – Tolaso Jul 5 '16 at 4:49
• I would agree that, for every symmetric matrix I've examined, there has existed an invertible matrix P that diagonalizes the symmetric matrix, but in general I don't know why that should be. I also agree that if I could establish that A is diagonalizable, I would know that it has $n$ eigenvectors – M. Gruben-Trejo Jul 5 '16 at 15:13
• This link appears to provide a superbly concise explanation of how I would know that every symmetric matrix is diagonalizable, however it relies on the application of the conjugate transpose. If that's required for this proof, then that's just as satisfying of an answer to me. – M. Gruben-Trejo Jul 5 '16 at 15:25
• Does it help to note that $Null((\lambda I - A)^\top) = Null(\lambda I - A) = Col(\lambda I - A)^\bot$? – M. Gruben-Trejo Jul 5 '16 at 22:12

## 1 Answer

Supposing symmetric matrix $An×n$, how do I know that there are $A$ eigenvectors of $A$?

Many people who are smarter than I am have already provided answers to this question. But out of extreme hubris, I didn't see why they were right, so I attempted the proof myself:

## Establishment of at least one Eigenvector of $A$

• Note that $A = A^\top$
• Note that, due to the fundamental theorem of algebra, $|\lambda I - A|=0$ must have at least 1 solution.
• Ergo, $\exists\lambda_1$, an eigenvalue of $A$.
• Since each distinct eigenvalue implies the existence of at least one eigenvector, a basis for that eigenspace, $\exists \vec{v_1}$, a unit eigenvector of $A$ (e.g. $||\vec{v_1}||=1$)

## Establishment of a Basis

• Let $B = \{\vec{v_1}, \vec{b_2}, ..., \vec{b_n}\}$, an orthonormal basis for $\mathbb{R}^n$, which is constructed from $\vec{v_1}$ by solving the system $\begin{bmatrix}{\vec{v_1}^\top}\end{bmatrix}=\vec{0}$.
• Let $P = \begin{bmatrix}\vec{v_1} & \vec{b_2} & ... & \vec{b_n}\end{bmatrix}$ $\therefore$ $P^\top = \begin{bmatrix}\vec{v_1}^\top\\ \vec{b_2}^\top\\ ...\\ \vec{b_n}^\top\end{bmatrix}$
• Note that, as $B$ has been defined as an orthonormal basis, $P^\top P = I_n \therefore P^{-1} = P^\top \therefore P$ is symmetric.

## Multiplication by $P$

• Note that $AP = \begin{bmatrix}A\vec{v_1} & A\vec{b_2} & ... & A\vec{b_n}\end{bmatrix}$
• Note that, since $\vec{v_1}$ is an eigenvector of $A$, $A\vec{v_1} = \lambda_1\vec{v_1} \therefore AP=\begin{bmatrix}\lambda_1\vec{v_1} & A\vec{b_2} & ... & A\vec{b_n}\end{bmatrix}$
• Note that $P^{\top}AP = \begin{bmatrix}\vec{v_1}^{\top}\lambda_1\vec{v_1} & \vec{v_1}^{\top}A\vec{b_2} & ... & \vec{v_1}^{\top}A\vec{b_n}\\ \vec{b_2}^{\top}\lambda_1\vec{v_1} & \vec{b_2}^{\top}A\vec{b_2} & ... & \vec{b_2}^{\top}A\vec{b_n}\\ \vdots & \vdots & & \vdots\\ \vec{b_n}^{\top}\lambda_1\vec{v_1} & \vec{b_n}^{\top}A\vec{b_2} & ... & \vec{b_n}^{\top}A\vec{b_n} \end{bmatrix}$

## Simplification

• Note that the first column of $P^{\top}AP$ can be rewritten as $\begin{bmatrix}\lambda_1(\vec{v_1}^{\top}\vec{v_1}) & \vec{v_1}^{\top}A\vec{b_2} & ... & \vec{v_1}^{\top}A\vec{b_n}\\ \lambda_1(\vec{b_2}^{\top}\vec{v_1}) & \vec{b_2}^{\top}A\vec{b_2} & ... & \vec{b_2}^{\top}A\vec{b_n}\\ \vdots & \vdots & & \vdots\\ \lambda_1(\vec{b_n}^{\top}\vec{v_1}) & \vec{b_n}^{\top}A\vec{b_2} & ... & \vec{b_n}^{\top}A\vec{b_n} \end{bmatrix}$
• Note that, since we have the dot product of orthonormal vectors in the first column, $P^{\top}AP$ simplifies to $\begin{bmatrix}1 & \vec{v_1}^{\top}A\vec{b_2} & ... & \vec{v_1}^{\top}A\vec{b_n}\\ 0 & \vec{b_2}^{\top}A\vec{b_2} & ... & \vec{b_2}^{\top}A\vec{b_n}\\ \vdots & \vdots & & \vdots\\ 0 & \vec{b_n}^{\top}A\vec{b_2} & ... & \vec{b_n}^{\top}A\vec{b_n} \end{bmatrix}$
• Note that, since we have the dot product of orthonormal vectors in the first column, $P^{\top}AP$ simplifies to $\begin{bmatrix}1 & \vec{v_1}^{\top}A\vec{b_2} & ... & \vec{v_1}^{\top}A\vec{b_n}\\ 0 & \vec{b_2}^{\top}A\vec{b_2} & ... & \vec{b_2}^{\top}A\vec{b_n}\\ \vdots & \vdots & & \vdots\\ 0 & \vec{b_n}^{\top}A\vec{b_2} & ... & \vec{b_n}^{\top}A\vec{b_n} \end{bmatrix}$
• Note that $(P^{\top}AP)^\top = P^{\top}A^{\top}(P^{\top})^\top = P^{\top}AP \therefore P^{\top}AP$ is symmetric.
• Since $P^{\top}AP$ is symmetric, it must be that $P^{\top}AP = \begin{bmatrix}1 & 0 & ... & 0\\ 0 & \vec{b_2}^{\top}A\vec{b_2} & ... & \vec{b_2}^{\top}A\vec{b_n}\\ \vdots & \vdots & & \vdots\\ 0 & \vec{b_n}^{\top}A\vec{b_2} & ... & \vec{b_n}^{\top}A\vec{b_n} \end{bmatrix}$

## Recursion

• Since $P^{\top}AP$ is symmetric, it must be that the block matrix formed by removing the first row and first column of $P^{\top}AP$ is also symmetric; that is, $\begin{bmatrix}\vec{b_2}^{\top}A\vec{b_2} & ... & \vec{b_2}^{\top}A\vec{b_n}\\ \vdots & & \vdots\\ \vec{b_n}^{\top}A\vec{b_2} & ... & \vec{b_n}^{\top}A\vec{b_n} \end{bmatrix}$ is symmetric.
• Now, we're back to the very beginning, namely supposing a symmetric matrix, although now of $B_{n-1\times n-1}$.

## Base Case

• Note that, for any $A_{k\times k}$ where $k < n$, we'll still have leftover symmetric matrix to pull eigenvectors from, and we don't need to consider a base case.
• However, when $k = n$, that is when we're actually considering a symmetric matrix with the same number of columns and rows as the dimension of the space, eventually (i.e., for our very last eigenvector) we'll get down to a symmetric submatrix denoted $M_{1\times 1}$, that is $M = \begin{bmatrix}k\end{bmatrix}$ where $k \in \mathbb{R}$.
• For this 1-by-1 matrix, note that $|\lambda I - M| = 0 = \lambda - k$, $\therefore \lambda_0 = k$, $\therefore$ the eigenvector $\begin{bmatrix}1\end{bmatrix}$ forms a basis for the eigenspace of $M$, $\therefore P = \begin{bmatrix}1\end{bmatrix}$.
• Note that, since $P = \begin{bmatrix}1\end{bmatrix}$, $P^{\top}MP = \begin{bmatrix}1\end{bmatrix}\begin{bmatrix}k\end{bmatrix}\begin{bmatrix}1\end{bmatrix} = \begin{bmatrix}k\end{bmatrix} = M$, $\therefore P$ orthogonally diagonalizes $M$, which is actually already diagonalized, being a 1-by-one matrix.

Some additional links to helpful proofs follow.

http://www.swarthmore.edu/NatSci/dmcclen1/math028S/m028f2011realspectral.pdf
https://math.berkeley.edu/~ogus/old/Math_54-05/webfoils/symmetric.pdf
https://www.math.ucdavis.edu/~linear/old/notes22.pdf