When given the matrix $A$, how do I find integer matrices $C$ and $D$ so that $CAD$ is diagonal?

Question

When given the matrix $A$, how do I find integer matrices $C$ and $D$ so that $CAD$ is diagonal? To be more specific, I am looking for $C$ and $D$ when $A$ equals:

$$ \begin{pmatrix} 2 & 1 & 2 \\\ 1 & 2 & 2 \\\ 2 & 3 & 0 \\\ \end{pmatrix} $$

I have an idea how to find $S$ so that $S^{-1} A S$ is diagonal, but that's not the only type of matrices $C$ and $D$ that exist. Also, how do I find integer ones specifically?

Answer 1

Let $C=(c_{ij})$ and $D=(d_{ij})$ two integer matrices. Then $CAD=diag(r_1,r_2,r_3)$ is equivalent to a system of Diophantine equations. This is difficult to solve in general. However, it is possible to find some interesting solutions, i.e., except for $C=0$ or $D=0$. Since $10A^{-1}$ has integer coefficients we obtain the solution $$ C=\begin{pmatrix} 6 & -6 & 2 \cr -4 & 4 & 2 \cr 1 & 4 & -3 \end{pmatrix},\; D=\begin{pmatrix} 1 & 0 & 0 \cr 0 & 1 & 0 \cr 0 & 0 & 1\end{pmatrix}. $$ Then we have $$ CAD=\begin{pmatrix} 10 & 0 & 0 \cr 0 & 10 & 0 \cr 0 & 0 & 10\end{pmatrix}, $$ which is a diagonal matrix.

Answer 2

It is always possible to find matrices $C$ and $D$ so that $CAD$ is diagonal, with only $0$ and $1$ along the diagonal. If $A$ has rational entries, then so will $C$ and $D$, so you can multiply each by the LCD of its entries to get an integer matrix. In fact, if you augment $A$ by the identity and then row-reduce it to its RREF, then the matrix on the right-hand side, scaled appropriately, will be your $C$. If $A$ has full rank, you can stop here and take $D=I$. Otherwise, augment the transpose of the rref with the identity and row-reduce again. The transpose of the right-hand matrix, also suitably scaled, will be your $D$.

If $A$ has irrational entries, on the other hand, then in general it might not be possible to find a common scale factor that will make all of the entries integral.

Using your example, the augmented RREF matrix ends up being $$\left(\begin{array}{ccc|cc}1&0&0 & \frac35&-\frac35&\frac15 \\ 0&1&0 & -\frac25&\frac25&\frac15 \\ 0&0&1 & \frac1{10}&\frac25&-\frac3{10}\end{array}\right).$$ The LCM of the entries on the right is $10$, therefore $$C = \begin{pmatrix}6&-6&2\\-4&4&2\\1&4&-3\end{pmatrix}$$ and, since $A$ has full rank, $D=0$.

If we start instead with $$A=\begin{pmatrix}2&4&2\\1&3&2\\2&2&0\end{pmatrix},$$ the augmented RREF is $$\left(\begin{array}{ccc|cc}1&0&-1 & 0&-\frac12&\frac34 \\ 0&1&1 & 0&\frac12&-\frac14 \\ 0&0&0 & 1&-1&-\frac12\end{array}\right),$$ so that $$C=\begin{pmatrix}0&-2&3\\0&2&-1\\4&-4&-2\end{pmatrix}.$$ $A$ does not have full rank, so form $$\left(\begin{array}{ccc|cc}1&0&0 & 1&0&0 \\ 0&1&0 & 0&1&0 \\ -1&1&0 & 0&0&1 \end{array}\right)$$ and row-reduce, eventually producing $$D=\begin{pmatrix}0&0&1\\1&1&-1\\-1&0&1\end{pmatrix}.$$