Every matrix can be changed to a symmetric matrix through elementary column operations

Question

The following question is given in a section 2 lecture of linear algebra. The first section is about polynomial, so the lectures just started to talk about determinants and matrices.

Let $A$ be an $n\times n$ matrix over a number field $F$. Then there exists an invertible matrix $R$ such that $AR$ is symmetric.

I know that this question can be (elegantly) eliminated using Jordan canonical form.

But since the question is left to who just learn linear algebra, I don’t think Jordan form is necessarily required.

Then the question can be interpreted as the following:

Let $A$ be an $n\times n$ matrix over a number field $F$. Then $A$ can be changed to a symmetric matrix through elementary column operations.

The Jordan form method only establishes the existence of some invertible matrix satisfying this property, which (I think) makes it unclear how to relate it with row/column operations.

I think it may be dealt with by induction. Am I right? It is not very clear to me how to complete the inductive steps. Any help is sincerely appreciated.

Answer 1

It is not really clear from your question what type of proof is needed. To me it is also not clear how to proceed by some induction argument, so I suppose that some knowledge is required. As for the Jordan form, I think it does not solve this question in full generality since it requires the algebraic closedness of $F$.

The proof will be based on the well-known fact that arbitrary matrix $A$ can be represented in the form $$ A = SI_rQ,$$ where $S$ and $Q$ are invertible and $I_r$ can be represented in the block form as $$I_r = \left(\begin{matrix} I & 0 \\ 0 & 0 \end{matrix}\right) $$ with the $r \times r$ identity matrix as the left upper block. Using that we obtain $AQ^{-1}S^T = SI_rS^T$ is symmetric.

The fact that we used above is quite easy to prove by considering a pair of basises in $F^n$ in which the matrix has the form $I_r$. That is consider arbitrary basis $e_1, \dots, e_r$ in $\mathrm{im} A = \{Ax: x \in F^n\}$ (here $r = \mathrm{rank} A$). Let $f_1, \dots, f_r$ be arbitrary preimages of $e_1, \dots, e_r$. Let $f_{r+1}, \dots, f_n$ be arbitrary basis in $\ker A$. Also arbitrarily extend $e_1, \dots, e_r$ by $e_{r+1}, \dots, e_n$ to a basis in $F^n$. Then $A$ has the form $I_r$ in the pair of basises $e$ and $f$, that is $A = SI_rQ$, where columns of $Q^{-1}$ are the vectors $f_i$ and the columns of $S$ are $e_i$.

Answer 2

1. First, find a matrix $R_1$ and a a permutation matrix $P$ such that $$ PAP^TR_1= \begin{pmatrix} U & O\\ V & O \end{pmatrix}, $$ where $U$ is an invertible matrix.

2. Now we will look for matrix $R_2$ in the form $$ \begin{pmatrix} X & Z\\ 0 & Y \end{pmatrix}, $$ where $Y$ is an invertible matrix and $UX=S$ is an invertible symmetric matrix. We have $$ (PAP^T)R_1R_2= \begin{pmatrix} UX & UZ\\ VX & VZ \end{pmatrix}= \begin{pmatrix} S & UZ\\ VX & VZ \end{pmatrix}. $$ We find the matrix $Z$ from the condition $$ UZ=(VX)^T\Rightarrow $$ $$ Z=U^{-1}X^TV^T=U^{-1}(U^{-1}S)^TV^T=U^{-1}SU^{-T}V^T=U^{-1}S(VU^{-1})^T. $$ It follows that $VZ=V(U^{-1}S(VU^{-1})^T)=(VU^{-1})S(VU^{-1})^T$ and so the matrix $PAP^TR_1R_2$ is symmetric.

3. Then the matrix $P^{-1}(PAP^TR_1R_2)P^{-T}=AP^TR_1R_2P^{-T}$ is still symmetric and hence the matrix $R=P^TR_1R_2P^{-T}$ is the desired matrix.

Note. I had to correct my original answer a bit, thanks again to Matsmir, who drew my attention to the flaw in the first answer

A short solution to the problem.

Let $P$ and $Q$ matrices correspond to those elementary transformations of the matrix $A$ which bring it to the diagonal form $D$. We have $$ PAQ=D. $$ The matrix $P^{-1}DP^{-T}$ is symmetric and $AQ P^{-T}=P^{-1}DP^{-T}$

Answer 3

This follows from (a) the existence of polar decomposition and (b) from the observation that every unitary matrix is a product of elementary matrices.

Answer 4

Assume first that $A$ is nonsingular and that we have $AR=S$, where $S$ is symmetric, and see what are the conditions for which there exist $R,S$ such that this equality holds.

We can vectorize the equality to get

$$(I\otimes A)\mathrm{vec}(R)=\mathrm{vec}(S).$$

If $A$ is invertible, then so is $I\otimes A$, and the problem is pretty much over. What this says that one can map $A$ to any symmetric matrix $S$. In that case, $R$ is automatically invertible whenever $S$ is. This is due to the fact $\det(S)=\det(A)\cdot\det(R)\ne 0$.

However, when $A$ is singular it is a bit more complicated and one has to make sure that $\mathrm{vec}(S)$ lies in the column space of $I\otimes A$. This is equivalent to saying that for all $v\in\mathbb{R}^{n^2}$, $v^T(I\otimes A)=0$ implies that $v^T\mathrm{vec}(S)=0$. This can be simplified to $w^TS_i=0$ for all $i=1,\ldots,n$, where $w$ is any vector in the left null-space of $A$ and $S_i$ is the $i$-th column of $S$. This imposes a certain structure on the matrix $S$ in terms of $q$ equality constraints per column where $q$ is the dimension of the null-space of $A$. So, this is $nq$ constraints plus $n(n-1)/2$ constraints imposed by the symmetric structure.

For instance, if $$A=\begin{bmatrix}0 & 1\\ 0 & -2\end{bmatrix}$$ and we have that $w=\begin{bmatrix}2 & 1\end{bmatrix}^T$ which means that the columns of $S$ must satisfy $2S_{11}+S_{21}=0$ and $2S_{12}+S_{22}=0$. Since $S$ is symmetric, we also have that $S_{12}=S_{21}$. This yields

$$S=\begin{bmatrix}S_{11} & -2S_{11}\\ -2S_{11} & S_{11}\end{bmatrix}$$ together with

$$R=\begin{bmatrix}R_{11} & R_{12}\\ S_{11} & -2S_{11}\end{bmatrix}$$

where $R_{11}$, $R_{12}$, and $S_{11}$ are arbitrary and can be chosen such that $R$ is nonsingular.