3
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ – Harald Hanche-Olsen May 2 '13 at 7:56
  • $\begingroup$ Both matrices have an unique row reduced echelon form. If their reduced echelon forms are different, then they are not equivalent, and conversely. $\endgroup$ – Fredrik Meyer May 2 '13 at 10:13
3
$\begingroup$

This is an attempt at creating a lower bound for the number of operations required.

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.

$\endgroup$
2
$\begingroup$

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...

Looking closely at the reduction to reduced row echelon form, you could probably get a bound on how long it takes (if you do row operations, not just keep switching rows for example) from the size of the matrices (if they both reduce to the identity, they would be row equivalent for example).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.