Matrix similarities using "maximally simple scalars" (in some sense).

Question

So I know there are in some sense more matrices $\bf A$ which are diagonalizable over $\mathbb C$ than over $\mathbb R$. I also suppose the same extends in general; Easier to find diagonalization the more complicated scalars we allow(?) Assuming the matrix elements $a_{ij}$ $\in \mathbb R$. Is there some way to define matrix similarities $${\bf A = T}^{-1} \bf CT$$ so that $\bf C$ is both maximally sparse and has simple scalars. I would consider binary $\{0,1\}$ elements the most simple possibility. In other words $\bf C$ being a permutation matrix. Do there exist any famous or well-known decompositions which do this in some sense?

Answer 1

As you express it, $A$ and $C$ are similar matrices. If the diagonalization of a real matrix $A$ would require complex eigenvalues, we can avoid this by using $2\times 2$ real Jordan blocks along the diagonal.

The eigenvalues of a permutation matrix are cyclotomic roots (roots of unity), so this is not often a possibility for $C$.

If $A$ is indeed diagonalizable, then its algebraic and geometric multiplicities of chararacteristic roots (eigenvalues) agree. It follows that $A$ will be similar to the companion matrix of its characteristic polynomial. In many applications the coefficients of the characteristic polynomial are "simpler" than the characteristic roots, so this might be the sort of thing you want. The companion matrix is very sparse; for example the Frobenius companion matrix form has a column with the non-leading polynomial coefficients and subdiagonal entries $1$ (otherwise zero).

An argument can be offered that companion matrix entries (the coefficients of the characteristic polynomial) are as simple, collectively, as any that suffice for the purpose. That is, these coefficients are obtained by adding, subtracting, and multiplying the entries of $A$ (ring operations), and by the same token can be obtained similarly from the entries of any matrix $C$ which is similar to $A$. So if $C$ is the similar matrix to $A$ with "simplest possible" entries, the entries of the companion matrix are almost as simple, being drawn from the same ring as entries of $C$.

If $A$ is not diagonalizable, then the rational canonical form or Frobenius normal form (also Frobenius-Perron normal form) will serve essentially the same purpose. That Wikipedia article is a good introduction, though the links it provides to algorithms are not in the best shape at present. Two of them point to a 1998 paper by Arne Storjohann, "An $O(n^3)$ Algorithms for the Frobenius Normal Form" (one of these is broken, the other leads to a paywall; a working link is here). The third link is to a 2002 note by K.R. Matthews, "A Rational Canonical Form Algorithm," which lays out clearly the relationship to companion matrices, referring to representations over invariant subspaces as hypercompanion matrices.