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?
With a bit extra poking around, I've found on the Wikipedia page Definite system matrix that, for the case where
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.)