# Sparsest similar matrix

Given a square matrix A (say with complex entries), which is the sparsest matrix which is similar to A?

I guess it has to be its Jordan normal form but I am not sure.

Remarks:

• A matrix is sparser than other if it has less nonzero entries.

• Two square $$n \times n$$ matrices $$A,C$$ are similar if there exists and invertible matrix $$P$$ such that $$A = P^{-1}CP$$

• If the matrix is diagonalisable, clearly its Jordan form is the sparsest one in its similarity class because you cannot get fewer than $\operatorname{rank}(A)$ entries. – user1551 Oct 19 at 11:32
• My intuition says the same, but apart from trivial cases ($A$ is diagonaliseable) I do not see an immediate proof of that. – TZakrevskiy Oct 19 at 11:32
• Simulposted to MO, mathoverflow.net/questions/313224/sparsest-similar-matrix DON'T DO THAT! – Gerry Myerson Oct 19 at 12:00

## 1 Answer

The companion matrix to the polynomial $$(x^2-1)^2=1-2x^2+x^4$$ is $$\pmatrix{0&0&0&-1\cr1&0&0&0\cr0&1&0&2\cr0&0&1&0\cr}$$ which has Jordan form $$\pmatrix{1&1&0&0\cr0&1&0&0\cr0&0&-1&1\cr0&0&0&-1\cr}$$ which has more nonzero entries.

• The following paper claims that the companion matrix is the sparsest in a certain sense: doi.org/10.1016/j.laa.2012.08.017 – Julian Kuelshammer Oct 19 at 13:24
• That is an interesting example. But if we call the first matrix $A$ and the second one $C$, to me it seems (motivated by Jordan normal form definition) among all matrices that are NOT equal to $A$, $C$ is the sparsest similar matrix to $A$. Can your example be generalized to prove my statement is incorrect? – abolfazl Oct 19 at 16:41
• You can always get a different but equally sparse matrix by conjugating by some diagonal and/or permutation matrix . . . – Noam D. Elkies Oct 19 at 18:34