Psychology 613<br>
Data Analysis III<br>
Prof. Bertram Malle<br>
Spring 1997<P></I>
<HR>
<font size = 3>
<h2>Determining Linear Dependence and Rank</h2>

To find a matrix's rank via its linearly dependent vectors, you can
either (a) look at the columns or the rows and try to "see" the
dependences or (b) use a systematic method.<p>

Method (a) works fine for all 2 x 2, 2 x p, and some 3 x 3 matrices
that have obvious linear dependences.  For example: <pre>
1 2    9 3    7  2  1     3  2  11    2  8  5
2 4    6 2    4  1  5     2 -1   5    5  5 -3
             14  4  2     1  4   6   -3  3  8</pre>

For more difficult (Square or rectangualr) matrices we need to turn to
the systematic method that uses echelon matrices.  

<h3>Echelon matrices</h3>

These matrices are results of systematic transformations of the
original matrix such that one can easily see (and count) the linearly
dependent (or independent) rows or columns.  The transformations
comprise only elementary operations (scalar multiplications and
weighted sums), and they are performed repeatedly until the matrix reaches a
certain form.  This "echelon form" is strictly defined: Any row that
has nonzero elements starts out with 1, and any row below it has
a 0 in that column where the upper row has a 1; the first nonzero
element of this next row also starts with a 1.<p>

That is, the first row of the echelon matrix starts out with 1; the
next row starts out with 0 (right below the 1 in the previous row)
and can then itself have a 1; the next starts out with 0, 0, and then
perhaps a 1, and so on. (Later rows may have all 0's.)  An echelon
matrix looks a little bit like a correlation matrix (most diagnoals
are 1's) and a little bit like a diagnoal matrix (at least the lower
off-diagnonals are all 0's).  Examples of echelon matrices are
displayed below:<pre>

1  2  -2     1  2 -4  3
0  1  -4     0  1  2 -0.5
0  0   1     0  0  1 -2
             0  0  0  1</pre> Both matrices shown are of full rank
because all rows have at least one nonzero element.  Any row of an
echelon matrix that has only 0's is linearly dependent on other rows
and thus reduces the rank of the matrix.  You can thus determine the
rank of the echelon matrix (and thus of the original matrix) by
simply counting the number of rows that have at least one nonzero element
(which should be a 1). <p>

So how do you get a matrix into echelon form?  You first look at the
first row (r1) and find a scalar that makes r1's first element into a
1.  Then you look at r2 and choose a weighted sum that makes r2's
first element into a 0 and its second element into a 1.  You proceed
down the remaining rows until you have all of them in perfect echelon
form or else reach a row that ends up having only 0's.  Then you can
stop. <p>

Let's go
through a few examples with the sample matrices displayed earlier.
<pre>
      1 2  # first row is already fine
      2 4  # second row needs to start out with a 0, so we'll subtract
             the first row twice from the second row, which should
	     make a 0 out of the 2 in the second row. But when we do
	     that [(2, 4) - 2(1, 2)] we realize that r2 becomes (0,
	     0).  Thus, this matrix has a rank of 1. 

-------------

 7  2  1      # r1 needs to be divided by 7 to start out with 1
 4  1  5
14  4  2

 1  2/7  1/7   
 4   1    5   # r2 should start out with 0, so we'll subtract 4 times
14   4    2     r1 from it, making it (0, -1/7, 4 3/7), but then we
                still need to multiply it by -7 to make the second
		element into a 1.

 1  2/7  1/7  # first two rows are fine now.
 0   1  -31
14   4    2   # r3 must start out with two 0's.  To make it easier to
                handle, let's first multiply it by 1/2, making it (7,
		2, 1); but that is the same vector originally
		presented by r1, so we know there is a linear
		dependence.  To complete the operation, we can just
		subtract 7 times the new r1 from the new r3 and we'll
		see that r3 becomes a row of 0's. This matrix has a
		rank of 2. 

---------------

   2  8  5   # r1 times 1/2 makes it (1, 4, 2.5), subtracting this      
   5  5 -3     five times from r2 makes (5, 5, -3) - 5(1, 4, 2.5) = 
  -3  3  8     (0, -15 -15.5); multiplying by -1/15 turns r2 into the
               right form.

   1  4  2.5
   0  1  31/30
  -3  3   8    # r3 needs to start out with 0 and 0, so let's do it
                 step by step; adding 3r1 gives (0, 15, 15.5); earlier
		 we saw this exact vector (but with negative signs)
		 showing up as r2, so we know that r3 is redundant.
</pre>


If you want to practice this method, show that the first three  matrices
below have full rank and that the next three don't.<pre>
2 1   1 2 4   3 6 12    1 2 3    4 6 10   1  2 -1  4  
7 4   2 1 3   2 6  2    4 5 6    1 0 16   2  1  1  0
      3 2 3   4 6  8    7 8 9    1 2 -2   4  3  2 -1
                                          5 4.5 1 3.5</pre>