3

What is the most that a matrix can be simplified if row or column operations are both allowed? Intuitively, I am guessing that everything is 0 except the diagonal entries, which are a mix of 0's and 1's. However, I'm unable to conjecture how many of the diagonal entries are 0's or 1's. I am lacking a solid proof of my understanding...

I haven't learned about rank, or null, or dimension, or kernels yet. I've just learned about invertibility, multiplication by elementary matrices, REF, RREF, row reduction, and block matrices.

Any help?

1 Answers1

3

Your intuition is correct. The number of $0$'s on the main diagonal is equal to the dimension of the kernel of the matrix. It is clear that any square matrix can be diagonalized when using both row and column operations. It is also clear that the non-zero entries on the main diagonal can then be normalized to $1$.

Now, if a matrix $B$ is obtained from a matrix $A$ by performing row operations, then $B=PAP^{-1}$ for some matrix $P$. The kernel of $B$ is then precisely $P(Ker(A))$, and (as $P$ is invertible) the dimension of the kernel of $B$ is equal to the dimension of the kernel of $A$.

A similar argument works for column operations. It now follows by induction on the number of operations performed that if $B$ is obtained from $A$ by performing any finite number of either row or column operations, then the dimension of the kernel of $A$ is equal to the dimension of the kernel of $B$. In particular then, if $B$ thus obtained is diagonal, then the dimension of its kernel is clearly equal to the number of $0$'s on the main diagonal, which is thus equal to the dimension of the kernel of $A$.

This is a baby version of Sylvester's Law of Inertia.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • Oh, I haven't learned about kernels or dimensions yet... –  Jul 24 '13 at 22:23
  • The kernel of $A$ is the set of all vectors $v$ such that $Av=0$. The dimension of a vector space is the maximal size of a linearly independent set. You probably will need to practice with these things a bit before you can understand the answer. This is standard material so you'll find it in many sources. – Ittay Weiss Jul 24 '13 at 22:25