For which matrices is it possible to find the (unreduced, and with arbitrary pivot) Echelon form of a matrix following Gaussian elimination, but only with the row operations:
- Adding/subtracting one row to another row (or any integer multiple)
- Swapping rows
For example, the matrix
$$\left(\begin{matrix}4&5\\2&9\end{matrix}\right)$$
can trivially be reduced using only single row addition. First
$$\left(\begin{matrix}0&-13\\2&9\end{matrix}\right)$$
then swapping rows
$$\left(\begin{matrix}2&9\\0&-13\end{matrix}\right)$$
we find the echelon form.
Is there a well-defined class of matrices (with any real numbers, but presumably rationals?) for which this is possible?
Given the column
$$\left(\begin{matrix}x\\y\end{matrix}\right)$$
We can use iterative row additions, where one row addition of row 1 with integer multiple $a$ gives
$$\left(\begin{matrix}x\\y+a x\end{matrix}\right)$$
which can be expressed with the matrix $A$,
$$\left(\begin{matrix}x'\\y'\end{matrix}\right)=\left(\begin{matrix}1&0\\a &1\end{matrix}\right)\left(\begin{matrix}x\\y\end{matrix}\right)=\left(\begin{matrix}x\\y+a x\end{matrix}\right)$$
Then we apply $b$ times row 2 to row 1 using the matrix $B$,
$$\left(\begin{matrix}x'\\y'\end{matrix}\right)=\left(\begin{matrix}1&b\\0 &1\end{matrix}\right)\left(\begin{matrix}x\\y\end{matrix}\right)=\left(\begin{matrix}x+by\\y\end{matrix}\right)$$
Then we can consider the goal, which is to find a matrix $C$ such that
$$\left(\begin{matrix}x'\\y'\end{matrix}\right)=\left(\begin{matrix}\alpha&\beta\\ &\end{matrix}\right)\left(\begin{matrix}x\\y\end{matrix}\right)=\left(\begin{matrix}0\\y'\end{matrix}\right)=\left(\begin{matrix}\alpha x+\beta y\\y'\end{matrix}\right)$$
we also can identify immediately that $\alpha=ly$ and $\beta=-lx$ for some integer $l$.
Therefore, for a given rational $x,y\in\mathbb Q$, it is possible to find a Echelon form of the matrix, if and only if the matrix C exists within the group generated by $A,B$. I.e., if
$$C\in\langle A,B\rangle$$
This group is $SL(2,\mathbb Z)$ as given in this question
Group generated by matrices with integers off the diagonal
Now consider $x,y\in\mathbb Q$. We write $x=u_x/v$ and $y=u_y/v$ where $u_x,u_y\in\mathbb Z$ are integers such that either $\text{gcd}(u_x,u_y)=1$, and $v\in\mathbb R$ is any real number.
Then we identify that a matrix with the following coefficients would row reduce our column.
$$\left(\begin{matrix}x'\\y'\end{matrix}\right)=\left(\begin{matrix}u_y&-u_x\\ c&d\end{matrix}\right)\left(\begin{matrix}u_x/v\\u_y/v\end{matrix}\right)=\left(\begin{matrix}0\\ y'\end{matrix}\right)$$
So long as the determinant of this matrix is $1$, then it exists within $SL(2,\mathbb Z)$ and hence a series of row additions can be found to reduce $x'=0$
$$\det\left|\begin{matrix}u_y&-u_x\\ c&d\end{matrix}\right|=u_yd+u_xc=1$$.
This is a linear Diophantine equation and has solutions if and only if $\text{gcd}(u_x,u_y)=1$, which it is by our choice of $u_x$ and $u_y$.
What values can $x,y$ take? We wrote $x=u_x/v$ and $y=u_y/v$ where $u_x,u_y\in\mathbb Z,$ $v\in\mathbb R$ and $\text{gcd}(u_x,u_y)=1$.
First we can show that $x,y\in\mathbb Q$.
For any $x=u_x'/v_x$ and $y=u_y'/v_y$ with integer $u_x',v_x,u_y',v_y\in\mathbb Z$ we can always write
$$x=u_x'v_y/v_yv_x\quad \text{and}\quad y=u_y'v_x/v_xv_y$$
and then define $l=\text{gcd}(u_x'v_y,u_y'v_x)$ to express $x,y$ as
$$x=u_x/v\quad \text{and}\quad y=u_y/v$$
where
$$u_x=u_x'v_y/l\quad\text{and} \quad u_y=u_y'v_x/l \quad\text{and} \quad v=v_xv_yl$$
The effect on the total matrix
The effect of the row operations on the total matrix can therefore be calculated as
$$\left(\begin{matrix}x_1'&x_2'\\y_1'&y_2'\end{matrix}\right)=\left(\begin{matrix}u_{y_1}&-u_{x_1}\\ c&d\end{matrix}\right)\left(\begin{matrix}x_1&x_2\\y_1&y_2\end{matrix}\right)=\left(\begin{matrix}0&x_2u_{y_1}-y_2u_{x_1}\\x_1c+y_1d&x_2c+y_2d\end{matrix}\right)$$