Multi-Page Printing

10 1. Preliminaries consisting of the first n1 columns, then the next n2 columns, etc. This partitions the matrix A into rs submatrices Aij, where Aij denotes the block formed from the ith set of rows and the jth set of columns. The size of Aij is mi × nj. When an m×n matrix A and a n×q matrix B are partitioned conformally, the product AB can be computed with block multiplication. More precisely, suppose A has been partitioned as described above. Partition B by using the numbers n1,...,ns to partition the rows of B, and by using positive integers q1,...,qt to partition the columns. Block Aij is size mi ×nj and block Bjk is size nj ×qk, so the matrix product AijBjk is defined and has size mi × qk. The (i, k) block of C = AB is then ∑s j=1 AijBjk, where C is partitioned using the numbers m1,...,mr for the rows and q1,...,qt for the columns. This block multiplication formula follows from the ordinary matrix multiplication rule. As an example, consider an n × n matrix M partitioned into four blocks by using r = s = 2 with m1 = n1 = k and m2 = n2 = n − k. We then have M = A B C D , where A and D are square of orders k and n−k, respectively, while B is k ×(n−k) and C is (n−k)×k. Suppose now that the upper left-hand block A is invertible. We may then do a block version of the usual row operation used in Gaussian elimination (i.e., adding a multiple of a row to a lower row) by multiplying M on the left by the partitioned matrix L = Ik 0 −CA−1 In−k . The product is LM = A B 0 D − CA−1B . The square matrix D − CA−1B is called the Schur complement of A in M. Since det L = 1, we have det M = det LM = ( det A )( det(D − CA−1B) ) . If n − k = k (so n is even and k = n 2 ), we also have ( det A )( det(D − CA−1B) ) = det(AD − ACA−1B). 1.10. Invariant Subspaces Let T : V → V be a linear transformation. We say the subspace U is invariant under T , or T -invariant, if T (U) ⊆ U. Suppose dim(V) = n and dim(U) = k, where 1 ≤ k n. Let {b1,..., bk} be a basis for U. We can extend this set to get a basis, B = {b1,..., bk, bk+1,..., bn}, for V and consider the matrix [T ]B representing T relative to the B basis. Column j of [T ]B gives the coordinates of T (bj) relative to the B-basis. Since U is T -invariant, whenever 1 ≤ j ≤ k, the vector T (bj) is a linear combination of the first k basis vectors b1,..., bk. Hence,