# How many row operations separate two row-equivalent matrices $A$ and $B$?

This definition is from Hoffmann and Kunze.

Definition. If $A$ and $B$ are $m \times n$ matrices over the field $F$, we say that $B$ is row-equivalent to $A$ if $B$ can be obtained from $A$ by a finite sequence of elementary row operations.

Suppose I have two different matrices and I perform 999 elementary row operations on $A$ on paper and cannot get $B$, so I conclude that they are not row equivalent, but the 1000th step (which I did not do) makes them row equivalent.

My question is what is the meaning of "finite sequence of elementary row operations" in the above definition. Is it that Linear algebra is modern so we must resort to computers.

• Doing 999 elementary row operations on $A$ and not getting $B$ proves nothing, of course. At least, not unless you are following a plan supported by sound theory. – Harald Hanche-Olsen May 2 '13 at 7:56
• Both matrices have an unique row reduced echelon form. If their reduced echelon forms are different, then they are not equivalent, and conversely. – Fredrik Meyer May 2 '13 at 10:13

For an $n×m$ matrix, it takes at most $n−1$ row operations to reduce everything below the main diagonal to zeros, then it takes $n−1$ row operations to reduce as much as possible above the diagonal (this probably needs some more operations and some standard definition on what "as much as possible" means in order to be a real bound, because it needs to yield a unique result).
Then $n$ more operations to reduce the first number in each row to $1$ . Do this for both of your matrices, and you should be able to tell if they are row equivalent. This gives a lower bound for an upper bound of $6n−4$ operations. For invertible square matrices this is indeed an upper bound.
It just means that, after some $n < \infty$ row operations on $A$ (or you could have started with $B$), you get to $B$. No comment on if $n$ is computable just from that definition, but...