# Are Diagonally dominant Tridiagonal matrices diagonalizable?

I have searched this in the literature but could not find any reference, so I would like to post it here. Hope this is at the research level. Assume that $$A=\begin{vmatrix} a_1 & b_1 \\ c_1 & a_2 & b_2 \\ & c_2 & \ddots & \ddots \\ & & \ddots & \ddots & b_{n-1} \\ & & & c_{n-1} & a_n \end{vmatrix}$$ where $a_i< 0,\quad 0\leq c_i,b_i\quad \forall i \quad$, $a_1+b_1=0$, $c_{n-1}+a_n=0$ and $c_{i-1}+a_i+b_i=0,\quad 2\leq i\leq n-1$.

My test using matlab with random matrices and they all diagonalizable. This makes me believe that $A$ should be diagonalizable, however, I have not found a simple proof for it.

My question here is : is $A$ diagonalizable ? can we find a "simple" proof for it? Thank you for your time!

• Generically all matrices are diagonalizable, so I am not convinced that testing with random matrices tells us much... – Yemon Choi Dec 17 '16 at 17:56
• Randomly chosen matrices will almost certainly be diagonalizable---because having distinct eigenvalues is generic. So testing with samples won't reveal much. – David Handelman Dec 17 '16 at 17:57
• Beat me by a minute, because I made stupid typing errors! – David Handelman Dec 17 '16 at 17:58
• Do you require $a_n = 0$? (I.e., is the equation $a_i + b_i + c_i = 0$ supposed to hold for $i=n$) – Pat Devlin Dec 17 '16 at 18:15

### Counterexample:

$$\begin{bmatrix} -1 & 1 & 0 & 0\\ 0 & -1 & 1 & 0\\ 0 & 0 & -2 & 2\\ 0 & 0 & 2 & -2 \end{bmatrix}$$ is defective: its eigenvalues are $-1,-1, 0, -4$ (it is block triangular, so its eigenvalues are those of the $2\times 2$ blocks on the diagonal), but $A+I$ has rank 3.

### Strategy to construct it:

My first thought was: let's take all the $c_k$ equal to $0$ and make a Jordan block $$\begin{bmatrix} -1 & 1 \\ & -1 & 1\\ && \ddots & \ddots \\ &&& -1 \end{bmatrix}.$$ This almost works, but the last row has to be adjusted to satisfy the zero-sum condition. My idea was adjusting it by adding rows and columns (but the other natural idea of changing $c_{n-1}$ only can be made to work, too; see below). It is a known fact that if $T_{11}$ and $T_{22}$ have no eigenvalues in common, then $\begin{bmatrix} T_{11} & T_{12}\\ 0 & T_{22} \end{bmatrix}$ and $\begin{bmatrix} T_{11} & 0\\ 0 & T_{22} \end{bmatrix}$ are similar (proof: $$\begin{bmatrix} I & X\\ 0 & I \end{bmatrix} \begin{bmatrix} T_{11} & T_{12}\\ 0 & T_{22} \end{bmatrix} \begin{bmatrix} I & X\\ 0 & I \end{bmatrix}^{-1} = \begin{bmatrix} T_{11} & T_{12}+XT_{22}-T_{11}X\\ 0 & T_{22} \end{bmatrix},$$ and the Sylvester equation $T_{11}X-XT_{22}=T_{12}$ is solvable whenever $T_{11}$ and $T_{22}$ have disjoint spectra).

So I just took $T_{11}$ a Jordan block, $T_{22}$ any matrix with no eigenvalues in common with it, and I knew that the resulting matrix had to have a Jordan block, too, no matter what $T_{12}$ was.

### Alternate idea

Let's adjust the Jordan block by making the minimum possible change: alter $c_{n-1}$: $$A= \begin{bmatrix} -1 & 1 \\ & -1 & 1\\ && \ddots & \ddots \\ &&& -1 & 1\\ &&&& -1 & 1\\ &&&&1 & -1 \end{bmatrix}.$$ This matrix is still block triangular, so its eigenvalues are $n-2$ times $-1$, and then whatever the eigenvalues of $\begin{bmatrix}-1 & 1\\ 1 & -1\end{bmatrix}$ are. Does it still have a Jordan block, or is it diagonalizable? I guess it probably has a Jordan block: matrices with a Jordan block have more degrees of freedom, so I expect them to be "generic" among the matrices with multiple eigenvalues. Let's just throw it into Wolfram Alpha to check and hope it works. Bingo! Oh, wait, in retrospect it is obvious that it works, because $A+I$ has clearly rank $n-1$.

• You beat me to it! I was just typing this now. – Pat Devlin Dec 17 '16 at 18:31
• @DuyNguyen It did before you edited it. :) Anyway, there are counterexamples with $a_i\neq 0$ as well, I have modified the answer to show one. – Federico Poloni Dec 17 '16 at 18:50
• Is there some deeper underlying reason for this? Or are the OP's conditions simply not specific enough for any strong results to follow? That is, what was the thought process that generated this counterexample? – Emilio Pisanty Dec 18 '16 at 1:23
• @EmilioPisanty When I came up with my example (I've been scooped!) the thought process was (1) try to make it obviously not diagonalizable [e.g., in this case, the Jordan block in the top left does the trick], and (2) make it otherwise as simple as possible. Counterexamples are easy to come by, I'm sure. Another thought here is that you don't want to check "random" or "generic" things because those are diagonalizable. Instead, you want to think of small cases (2x2 and 3x3 don't yield counterexamples without thinking too long about it, so try 4x4). – Pat Devlin Dec 18 '16 at 3:58
• Ah, that's a nice fact to have around. Thanks for the insight! (and consider writing it into the answer). – Emilio Pisanty Dec 18 '16 at 10:52

All real tridiagonal matrices with $b_kc_k>0$, are diagonalizable, and their spectra are real and simple.

See, for example, Gantmakher and Krein, Oscillation matrices and kernels..., AMS 2002.

Sketch of the proof. Expanding the determinant $|A-\lambda I|$ write a recurrent formula for characteristic polynomials of truncated matrices. It is seen from this formula that the eigenvalues depend only on $a_k$ and the products $c_kb_k$. Therefore the symmetric matrix with $c_k^\prime=b_k^\prime=\sqrt{c_kb_k}$ has the same spectrum. This shows that the spectrum is real.

To show that all eigenvalues are distinct one applies Sturm's theorem to the sequence of characteristic polynomials.

On the other hand, if you allow all $c_k=0$, for example, you can have a Jordan cell which is not diagonalizable.

• I thought Jacobi matrices had to be symmetric? – Pat Devlin Dec 17 '16 at 18:36
• My sketch of the proof shows why the symmetry assumption actually does not restrict generality:-) – Alexandre Eremenko Dec 17 '16 at 18:40
• The hypotheses are that $b_k c_k \geq 0$. And we cannot set all $c_k$ equal to $0$ since the row cannot be all $0$. [And why does knowing the spectrum tell you that the thing is diagonal? The eigenvalues need not be distinct.] – Pat Devlin Dec 17 '16 at 18:49
• For an alternate proof: it is easy to construct a diagonal matrix $D$ such that $DAD^{-1}$ is symmetric. – Federico Poloni Dec 17 '16 at 19:06
• @Federico, in fact the old EISPACK system provided a routine (FIGI) for a diagonal similarity transformation for unsymmetric tridiagonals. – J. M. is not a mathematician Dec 17 '16 at 21:33