Linear Algebra Powertool

Constructing Random Matrices with specified rank

On Line Section 2.3

Worksheet by Michael K. May, S.J., revised by Russell Blyth

> restart: with(linalg): with(plots): with(plottools):

Warning, the protected names norm and trace have been redefined and unprotected

Warning, the name changecoords has been redefined

Warning, the name arrow has been redefined

Outline

This worksheet covers material similar to the On Line 2.3 section.

The basic objectives are:

• 1) Learn how to produce a random matrix of specified size and rank.
• 2) Explore how Maple finds a basis for the row space and column space of a matrix.
• 3) Relate the size of a matrix to the dimensions of the null space, the column space, and the row space.

Part1: Random matrices and rank

As we test out theories in linear algebra it is often useful to produce a random matrix with specified size and rank. While testing theories out on such matrices is not a substitute for doing proofs, it can help in convincing us that it is worth looking for a proof. That is actually much of the battle in mathematics.

Recall that the Maple command randmatrix(m,n); creates an m by n matrix with entries randomly chosen integers between -100 and 100. (To choose your own range of permissible entries, specify the range using a third argument, for example: randmatrix(m,n,entries=rand(-9..9)) ; ). Since the rank of a matrix is the number of nonzero rows in the reduced echelon form of the matrix, it is bounded by the minimum of m and n. It is worthwhile to note that the rank of a random matrix is usually actually equal to the minimum of m and n.

> A := randmatrix(4,5); rank(A);
B := randmatrix(6,3); rank(B);

Adjoining rows or columns that are linear combinations of the existing rows and columns of a matrix does not change the rank. In keeping with the random way we are constructing matrices, we will add random linear combinations of rows and columns. [The Maple command rand(a..b)(); produces a random integer in the range [a,b].]

> bigA := stackmatrix(A,
rand(-10..10)()*row(A,1)+rand(-10..10)()*row(A,2)+
rand(-10..10)()*row(A,3)+rand(-10..10)()*row(A,4));
rank(bigA);

> bigB := augment(B,
rand(-10..10)()*col(B,1) + rand(-10..10)()*col(B,2) +
rand(-10..10)()*col(B,3),
rand(-10..10)()*col(B,2) - rand(-10..10)()*col(B,3));
rank(bigB);

[Version warning - In Maple VR4, the command for stacking matrices is stack rather than stackmatrix.]

Exercises:

1) Generate 3 random matrices of the following sizes: 3 x 4; 6 x 3; and 4 x 7. Test the rank of these matrices and verify that it is the minimum of the number of rows and the number of columns.

>

2) Explain why we generally expect a random m by n matrix to have rank either m or n, and not to have smaller rank (think, for example, about the subspace of spanned by three randomly chosen vectors in ).

>

3) Use Maple to produce a 4 by 6 matrix of rank 3 named MyMatrix .

>

Finding bases for the row and column spaces

The Maple commands rowspace and colspace produce bases for the row space and the column space respectively. It should be noted that augmenting by linear combinations of columns does not change the column space and stacking linear combinations of rows does not change the row space.

> rbasA := rowspace(A); rbasbigA := rowspace(bigA);
cbasB := colspace(B); cbasbigB := colspace(bigB);

For the row space it is instructive to look at the reduced echelon form of the matrix, to see that its rows are used as a basis for the row space of the original matrix.

> gaussjord(bigA);

To find a basis for the column space it stands to reason that we want to choose the columns of a matrix that has been column reduced. To get Maple to do that for us we row reduce the transpose of the matrix and then transpose back.

> transpose(gaussjord(transpose(bigB)));

Read off a basis for the column space from the first three columns of the result.

Exercises:

4) Find bases for the row space and column space of MyMatrix defined above.

>

5) Use Maple to row reduce and column reduce MyMatrix, and verify that the bases found in Exercise 4 are the nonzero rows or columns of the reduced matrices.

>

Connecting the row space and the null space

In the last two exercises you should have noticed that the dimensions of the row space and the column space of a matrix are equal. In both cases this corresponds to the number of pivots in reduced echelon form of the matrix, that is, the rank of the matrix. We have noted in class that the dimension of the null space is the number of free variables in the reduced matrix. In Chapter 4 we will discover an important relationship between the vectors in the row space and the vectors in the null space (recall that both spaces are subspaces of if A ia an m x n matrix). This relationship involves the dot product extended naturally to . We check dot products to note that the vectors in the null space are orthogonal to the vectors in the row space (two vectors are orthogonal if their dot product is zero).

> rbasbigA := rowspace(bigA); nbasbigA := nullspace(bigA);

> dotprod(rbasbigA[1],nbasbigA[1]);
dotprod(rbasbigA[2],nbasbigA[1]);
dotprod(rbasbigA[3],nbasbigA[1]);
dotprod(rbasbigA[4],nbasbigA[1]);

Exercises:

6) Verify that the vectors in a basis for the row space of MyMatrix are orthogonal to vectors in a basis for the nullspace.

>

7) If we stack a random m by n matrix on top of a basis for its null space and use Gauss-Jordan elimination, what can you say about the the number of pivots and free variables in the resulting matrix?

>

>

>

>