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
\begin{equation}
\mathbf{K}\mathbf{u} = \lambda \mathbf{M}\mathbf{u}
\end{equation}
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{equation}
\begin{bmatrix}
1 & 1 \\ 0 & 1
\end{bmatrix}
\end{equation}
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?
 A: 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.
Proof (adapted from Wikipedia article)
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}$:
\begin{equation}
\mathbf{M}^{-1} = \mathbf{L}\mathbf{L}^*
\end{equation}
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.)
