Is this true: adding a random DIAGONAL perturbation can make a nondiagonalizable matrix diagonalizable? For any nondiagonalizable matrix $A\in\mathbb{R}^{n\times n}$, let $\hat{A}=A+E$ where $E$ is a small random DIAGONAL matrix (e.g. diagonal entries of $E$ are i.i.d. sampled from $N(0,\epsilon^2)$ for arbitrarilly small $\epsilon>0$). Can we conclude that $\hat{A}$ is diagonalizable with probability $1$ (Here $A$ is fixed and the randomness is only from $E$)?
My question is similar to this question, but here the perturbation matrix is required to be diagonal.
 A: Assuming we're diagonalizing over the complex numbers, yes. In fact, we can perturb $A$ such that all its eigenvalues are distinct, which will be more than good enough.
Some notation: let $A^{\mathsf L}$ be the $(n-1)\times(n-1)$ leading principal submatrix of $A$: the matrix with the last row and column of $A$ removed.
Lemma. If $\lambda$ is an eigenvalue of $A$ with algebraic multiplicity $>1$, then $\lambda$ is an eigenvalue of $A^{\mathsf L}$.
Proof. In general, $\lambda$ might not have as many eigenvectors as its algebraic multiplicity, but it has as many generalized eigenvectors as that. A vector $\mathbf x$ is a generalized $\lambda$-eigenvector of $A$ if $(A - \lambda I)^k \mathbf x = \mathbf 0$ for some $k$.
If $\mathbf x, \mathbf y$ are two generalized $\lambda$-eigenvectors of $A$, then any linear combination of them is also a generalized $\lambda$-eigenvector. In particular, the linear combination $\mathbf z = \frac1{x_n} \mathbf x - \frac1{y_n} \mathbf y$ has last coordinate equal to $0$. This makes $(z_1, \dots, z_{n-1})$ a generalized $\lambda$-eigenvector of $A^{\mathsf L}$, which can only happen if $\lambda$ is an eigenvalue of $A^{\mathsf L}$. $\quad\square$
Now we can go on to prove the main result. Let's pick $E$ in two steps: first, pick $E_{11}, E_{22}, \dots, E_{n-1,n-1}$ and second, pick $E_{nn}$. By induction, we can show that with probability $1$, $(A+E)^{\mathsf L}$ has all distinct eigenvalues. (This always holds for $n=1$.) We'll show that in that case, with probability $1$, the choice of $E_{nn}$ will preserve that property for $A+E$.
By the lemma, the only repeated eigenvalues we have to worry about are the $n-1$ eigenvalues of $A'$. Let $\lambda$ be one of those eigenvalues.
We can write the characteristic polynomial $f(x) = \det(A + E - x I)$ as $p(x) + E_{nn} q(x)$: just expand by minors along the last row. In particular, $q(x) = \det((A+E)^{\mathsf L} - xI)$, the characteristic polynomial of $(A+E)^{\mathsf L}$. If $\lambda$ is a repeated eigenvalue of $A+E$, then we have $f(\lambda) = f'(\lambda) = 0$. Because $\lambda$ was a single eigenvalue of $(A+E)^{\mathsf L}$, we also have $q(\lambda)=0$ but $q'(\lambda) \ne 0$. This lets us solve $f'(\lambda) = p'(\lambda) + E_{nn} q'(\lambda) = 0$ for $E_{nn}$: $\lambda$ can only be a repeated eigenvalue of $A+E$ if $E_{nn} = -\frac{p'(\lambda)}{q'(\lambda)}$.
So for each eigenvalue of $(A+E)^{\mathsf L}$, there is at most one value of $E_{nn}$ that will make it a repeated eigenvalue of $A+E$. With probability $1$, $E_{nn}$ avoids all those values, and so all eigenvalues of $A+E$ are distinct, completing the proof.
