# Do all generalised eigenvalue problems with Hermitian $N \times N$ matrices $\mathbf{K}$, $\mathbf{M}$ have $N$ linearly independent eigenvectors?

Consider the generalised eigenvalue problem

$$$$\mathbf{K}\mathbf{u} = \lambda \mathbf{M}\mathbf{u}$$$$

where both $$N \times N$$ matrices are Hermitian.

I am trying to prove that one can form an $$\mathbf{M}$$-orthonormal basis using $$N$$ eigenvectors, regardless of whether there exists any repeated eigenvalues. ($$\mathbf{M}$$-orthogonality refers to $$\mathbf{a}^*\mathbf{M}\mathbf{b} = 0$$, and normalisation of eigenvectors is according to $$\mathbf{a}^*\mathbf{M}\mathbf{a} = 1$$)

However, in the process of doing so, I realised that I had been assuming that solving the generalised eigenvalue problem will always spits out $$N$$ linearly independent eigenvectors. Indeed, this is not always true in the general case, as seen for solving the ordinary eigenvalue problem for the non-Hermitian matrix,

$$$$\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$$$$

which has eigenvectors that span only one dimension.

So, for generalised eigenvalue problems for Hermitian matrices $$\mathbf{K}, \mathbf{M}$$, is it possible to prove that it's always possible to obtain $$N$$ linearly independent eigenvectors? If not, under what additional conditions to Hermiticity are required?

With a bit extra poking around, I've found on the Wikipedia page Definite system matrix that, for the case where

• $$\mathbf{K}$$ is an $$N \times N$$ Hermitian matrix,
• $$\mathbf{M}$$ is an $$N\times N$$ Hermitian matrix and positive definite,

both matrices can be diagonalised simultaneously. From this, it can then be shown that $$N$$ linearly independent eigenvectors can be obtained. (Furthermore, it is possible to select the eigenvectors such that they are all $$\mathbf{M}$$-orthogonal.

If $$\mathbf{M}$$ is positive definite, it is invertible, and its inverse $$\mathbf{M}^{-1}$$ is also positive definite. Furthermore, since $$\mathbf{M}$$ is Hermitian, so is its inverse. Every positive definite Hermitian matrix has a Cholesky decomposition, so we can express a Cholesky decomposition for $$\mathbf{M}^{-1}$$:

$$$$\mathbf{M}^{-1} = \mathbf{L}\mathbf{L}^*$$$$

where $$\mathbf{L}$$ is a lower triangular matrix with real positive entries on the diagonal. Therefore, $$\mathbf{L}$$ is also positive definite, and can be inverted. Therefore, we can see that

$$\mathbf{M} = \left(\mathbf{L^{-1}}\right)^* \mathbf{L}^{-1}$$

or, equivalently

$$\mathbf{L}^* \mathbf{M}\mathbf{L} = \mathbf{I} \tag{1}\label{1}$$

This looks reminiscent of a similarity transformation from $$\mathbf{M}$$ to the identity $$\mathbf{I}$$. However, it is not quite, as $$\mathbf{L}$$ is generally not a unitary matrix. We can define a new matrix $$\mathbf{A}$$ by doing the same operation to $$\mathbf{K}$$:

$$\mathbf{L}^* \mathbf{K}\mathbf{L} = \mathbf{A} \tag{2}\label{2}$$

$$\mathbf{A}$$ is generally not diagonal. However, it can be readily shown that since $$\mathbf{K}$$ is Hermitian, then $$\mathbf{A}$$ is Hermitian. (In fact, if we let $$\mathbf{u} = \mathbf{L} \mathbf{v}$$, we can use Equations \eqref{1} & \eqref{2} to convert our generalised eigenvalue problem $$\mathbf{K}\mathbf{u} = \lambda \mathbf{M}\mathbf{u}$$ to the standard eigenvalue problem $$\mathbf{A}\mathbf{v} = \lambda \mathbf{v}$$)

Any complex matrix has a Schur decomposition $$\mathbf{A} = \mathbf{Q}\mathbf{T}\mathbf{Q}^*$$, where $$\mathbf{T}$$ is a triangular matrix, and $$\mathbf{Q}$$ is a unitary matrix. However, since in our case $$\mathbf{A}$$ is Hermitian, the triangular matrix is also Hermitian. A Hermitian triangular matrix must be a diagonal matrix! We will represent this matrix with $$\mathbf{D}$$:

$$\mathbf{A} = \mathbf{Q} \mathbf{D} \mathbf{Q}^*$$

or, equivalently,

$$\mathbf{Q}^* \mathbf{A} \mathbf{Q} = \mathbf{D}$$

Trivally, we may also express $$\mathbf{I}$$ as

$$\mathbf{Q}^* \mathbf{I} \mathbf{Q} = \mathbf{I}$$

Substituting Equations \eqref{1} & \eqref{2} into the above, and letting $$\mathbf{U} = \mathbf{L}\mathbf{Q}$$, we can now see that the operations that simulataneously diagonalise $$\mathbf{M}$$ and $$\mathbf{K}$$ are

$$\mathbf{U}^* \mathbf{M}\mathbf{U} = \mathbf{I} \tag{3}\label{3}$$

and

$$\mathbf{U}^* \mathbf{K}\mathbf{U} = \mathbf{D} \tag{4}\label{4}$$

By letting $$\mathbf{u} = \mathbf{U}\mathbf{q}$$, and substituting this and Equations \eqref{3} & \eqref{4}, we obtain the straightforward eigenvalue problem

$$\mathbf{D}\mathbf{q} = \lambda \mathbf{q}$$

whose $$n^\text{th}$$ solution is readily obtained: $$\lambda_n = D_{nn}$$ and $$\mathbf{q}_n = \mathbf{e}_n$$, where $$\mathbf{e}_n$$ is the unit column vector whose $$n^\text{th}$$ element is 1, with all other elements equal to 0.

Then, since $$\mathbf{u} = \mathbf{U}\mathbf{q}$$, we can see that the $$n^\text{th}$$ eigenvector of our original problem has the form

$$\mathbf{u}_n = \mathbf{U}\mathbf{e}_n$$

In other words, the columns of $$\mathbf{U}$$ are the eigenvectors of $$\mathbf{K}\mathbf{u} = \lambda \mathbf{M}\mathbf{u}$$.

Since $$\mathbf{U} = \mathbf{L}\mathbf{Q}$$, and $$\mathbf{L}$$ and $$\mathbf{Q}$$ are both invertible, it follows that $$\mathbf{U}$$ must also be invertible. As a result, this means that $$\mathbf{U}$$ must be full rank, which implies that the columns comprising the matrix must all be linearly independent.

Therefore, it is indeed possible to express $$N$$ linearly independent eigenvectors.

(In fact, since $$\mathbf{U}^* \mathbf{M}\mathbf{U} = \mathbf{I}$$, it is also clear that the linearly independent eigenvectors are also $$\mathbf{M}$$-orthogonal. Note that this $$\mathbf{M}$$-orthogonality still applies even between eigenvectors corresponding to repeating eigenvalues.)