Introduction To Linear Algebra - Calvin.edu

1.1 Matrix Algebraproducts ensures that things can be grouped differently with no change in theanswer—that is, so(BA)v B(Av) . Notice that the n-by-n matrixIn 1 0 : 0 . . 00 0 ···1 0 ···0 1 ···. . . . .0 0 ··· 0 0 0 . . 1has the property that, whenever C is an n-by-p matrix (so that the product In Cmakes sense), it is the case that In C C. Moreover, if B is an m-by-n matrix, thenBIn B. Since multiplication by In does not change the matrix (or vector) withwhich you started, In is called the n-by-n identity matrix. In most instances, wewill write I instead of In , as the dimensions of I should be clear from context.In Sage, the function that returns the n-by-n identity matrix is identity matrix(). This explains the result of the commandsB matrix(QQ, 2, 3, [1,2,3,2,3,-1])B * identity matrix(3) For a square (n-by-n) matrix A, there may be a corresponding n-by-n matrix Bhaving the property thatAB BA In .If so, the matrix A is said to be nonsingular or invertible, with inverse matrixB. Usually the inverse of A, when it exists, is denoted by A 1 . This relationshipis symmetric, so if B is the inverse of A, then A is the inverse of B as well. If Ais not invertible, it is said to be singular.The following fact about the product of invertible matrices is easily proved.Theorem 1: Suppose A, B are both n-by-n invertible matrices. Thentheir product AB is invertible as well, having inverse (AB) 1 B 1 A 1 .When A is invertible, it is not so easy to find A 1 as one might think. Executethe commands below. Would you have be able to guess the contents of theinverse matrix B?A matrix(QQ, [[1, 2, 3], [2, 3, -1], [1, 0, -2]])B A.inverse()7

1 Solving Linear Systems of Equationsshow(B)show(B.n())show(A*B)B*A4. Transposition of a MatrixLook closely at the two matrices 2 0 1 1 A 3 1 1 1 2 2 0 1and 1 3 2 2 1 2 B 10 0 1 1 1for a connection between the two. The matrix B has been formed from A so thatthe first column of A became the first row of B, the second column of A becamethe 2nd row of B, and so on. (One might say with equal accuracy that the rows ofA became the columns of B, or that the rows/columns of B are the columns/rowsof A.) The operation that produces this matrix B from (given) matrix A is calledtransposition, and matrix B is called the transpose of A, denoted as B AT . (Note:In some texts the prime symbol is used in place of the T , as in B A0 .)When you already have a matrix A defined in Sage, the transpose() method willtake produce its transpose:A matrix(QQ, 2, 3, [1, 2, 3, 2, 3, -1])show(A)C A.transpose()show(C)Remarks: If A is an m-by-n matrix, then AT is n-by-m. Some facts which are easy to prove about matrix transposition are the following:(i) For all matrices A it is the case that (AT )T A.(ii) Whenever two matrices A and B can be added, it is the case that (A B)T AT BT .(iii) Whenever the product AB of two matrices A and B is defined, it is the casethat (AB)T BT AT .(Compare this result to Theorem 1, a similar-looking fact about the inverseof the product of two invertible matrices.)(iv) For each invertible matrix A, AT is invertible as well, with (AT ) 1 (A 1 )T . There are some matrices A for which AT A. Such matrices are said to besymmetric.8

1.2 Matrix Multiplication and Systems of Linear Equations1.2 Matrix Multiplication and Systems of Linear Equations1.2.1 Several interpretations of matrix multiplicationIn the previous section we saw what is required (in terms of matrix dimensions) in orderto be able to produce the product AB of two matrices A and B, and we saw how to producethis product. There are several useful ways to conceptualize this product, and in this firstsub-section we will investigate them. We first make a definition.Definition 3: Let A1 , A2 , . . . , Ak be matrices all having the same dimensions. Foreach choice of real numbers c1 , . . . , ck , we callc1 A1 c2 A2 · · · ck Aka linear combination of the matrices A1 , . . . , Ak . The set of all such linear combinationsS : {c1 A1 c2 A2 · · · ck Ak c1 , . . . , ck R}is called the linear span (or simply span) of the matrices A1 , . . . , Ak . We sometimeswrite S span({A1 , . . . , Ak }).9

1 Solving Linear Systems of EquationsHere, now, are several different ways to think about product AB of two appropriatelysized matrices A and B.1. Block multiplication. This is the first of four descriptions of matrix multiplication,and it is the most general. In fact, each of the three that follow is a special case ofthis one.Any matrix (table) may be separated into blocks (or submatrices) via horizontal andvertical lines. We first investigate the meaning of matrix multiplication at the blocklevel when the left-hand factor of the matrix product AB has been subdivided usingonly vertical lines, while the right-hand factor has correspondingly been blockedusing only horizontal lines.Example 2:Suppose 8 8 3 4 5 A 6 6 1 8 6 5 3 4 2 7 hi A1 A2 A3 (Note how we have named the three blocks found in A!), and 3 5 5 2 2 2 2 7 B1 03 B2 .B 6 6 B3 3 2 5 0 0 1 1 4ThenAB A1 B1 A2 B2 A3 B3 # 3 4 8 8 "hi 3 5 5 2 1 6 6 0 3 8 6 6 2 22 7 245 3 8 24 24 72 18 18 0 9 12 13 30 42 42 30 6 6 0 3 24 22 9 19 19 31 24 24 0 12 6 3 14 29 9 43 12 26 8 57 . 39 40 36 9 #5 " 3 2 5 0 6 0 1 1 47 15 20 34 24 17 28While we were trying to keep things simple in the previous example by drawing onlyvertical lines in A, the number and locations of those vertical lines was somewhat10

1.2 Matrix Multiplication and Systems of Linear Equationsarbitrary. Once we chose how to subdivide A, however, the horizontal lines in B hadto be drawn to create blocks with rows as numerous as the columns in the blocks ofA.Now, suppose we subdivide the left factorSay that A11 A A21 A31with both horizontal and vertical lines.A12A22A32 . Where the vertical line is drawn in A continues to dictate where a horizontal linemust be drawn in the right-hand factor B. On the other hand, if we draw any verticallines in to create blocks in the right-hand factor B, they can go anywhere, paying noheed to where the horizontal lines appear in A. Say that#"B11 B12 B13 B14.B B21 B22 B23 B24Then A11 A12 " B11AB A21 A22 B21A31 A32 A11 B11 A12 B21 A21 B11 A22 B21 A31 B11 A32 B21B12 B13 B14B22 B23 B24#A11 B12 A12 B22 A11 B13 A12 B23 A11 B14 A12 B24A21 B12 A22 B22 A21 B13 A22 B23 A21 B14 A22 B24A31 B12 A32 B22 A31 B13 A32 B23 A31 B14 A32 B24 . Example 3:Suppose A, B are the same as in Example 2. Let’s subdivide A in the following(arbitrarily chosen) fashion: "# 8 8 3 4 5 A11 A12 A 6 6 1 8 6 .A21 A22 5 3 4 2 7Given the position of the vertical divider in A, we must place a horizontaldivider in B as shown below. Without any requirements on where verticaldividers appear, we choose (again arbitrarily) not to have any. 3 5 5 2 2 2 2 7 #" B103 B 6 6.B2 3 2 5 0 0 1 1 411

1 Solving Linear Systems of EquationsThen"AB A11 B1 A12 B2A21 B1 A22 B2# 3 hi 2 883 4 6 3 3 " # 6 6 1 8 2 5 3 4 2 6 3 14 29 9 43 12 26 8 57 . 39 40 36 95 2625 262 520 5 520 5 2 hi 7 5 0 1 1 4 3 0 2 " # i 7 6 h 0 1 1 4 3 7 02. Sums of rank-one matrices. Now let us suppose that A has n columns and B hasn rows. Suppose also that we block (as described allowed for in the previous caseabove) A by column—one column per block—and correspondingly B by row:A hA1 A2 · · ·Aniand B B1B2.Bn . Following Example 2, we getAB A1 B1 A2 B2 · · · An Bn nXA jB j .(1.1)j 1The only thing new here to say concerns the individual products A j B j themselves,in which the first factor A j is a vector in Rm and the 2nd B j is the transpose of a vectorin Rp (for some m and p).So, take u Rm and v Rp . Since u is m-by-1 and vT is 1-by-p, the product uvT ,called the outer product of u and v, makes sense, yielding an m-by-p matrix.12

1.2 Matrix Multiplication and Systems of Linear EquationsExample 4:Given u ( 1, 2, 1) and v (3, 1, 1, 4), their vector outer product is 1 h 3 1 1 4 i 2 2 8 .uvT 2 3 1 1 4 6 131 1 4If you look carefully at the resulting outer product in the previous example, youwill notice it has relatively simple structure—its 2nd through 4th columns are simplyscalar multiples of the first, and the same may be said about the 2nd and 3rd rowsin relation to the 1st row. Later in these notes, we will define the concept of therank of a matrix. Vector outer products are always matrices of rank 1 and thus, by(1.1), every matrix product can be broken into the sum of rank-one matrices.3. Linear combinations of columns of A. Suppose B has p columns, and we partitionit in this fashion (Notice that B j represents the jth column of B instead of the jth row,as it meant above!):hiB B1 B2 · · · Bp .This partitioning by vertical lines of the right-hand factor in the matrix product ABdoes not place any constraints on how A is partitioned, and so we may writehihiAB A B1 B2 · · · Bp AB1 AB2 · · · ABp .That is, for each j 1, 2, . . . , p, the jth column of AB is obtained by left-multiplyingthe jth column of B by A.Having made that observation, let us consider more carefully what happens whenA—suppose it has n columns A1 , A2 , . . . , An —multiplies a vector v Rn . (Note thateach B j is just such a vector.) Blocking A by columns, we haveAv hA1 A2 · · · i An v1v2.vn v A v A · · · v A .2 2n n 1 1 That is, the matrix-vector product Av is simply a linear combination of the columnsof A, with the scalars multiplying these columns taken (in order, from top to bottom)from v. The implication for the matrix product AB is that each of its columns AB j is alinear combination of the columns of A, with coefficients taken from the jth columnof B.13

1 Solving Linear Systems of Equations4. Linear combinations of rows of B. In the previous interpretation of matrix multiplication, we begin with a partitioning of B via vertical lines. If, instead, we beginwith a partitioning of A, a matrix with m rows, via horizontal lines, we get A1 A1 B A2 A2 B AB . B . . . . AmAm BThat is, the jth row of the matrix product AB is obtained from left-multiplying theentire matrix B by the jth row (considered as a submatrix) of A.If A has n columns, then each A j is a 1-by-n matrix. The effect of multiplying a 1-by-nmatrix V by an n-by-p matrix B, using a blocking-by-row scheme for B, is B1 i B2 h v B v B · · · v B ,VB v1 v2 · · · vn 2 2n n 1 1 · · · Bna linear combination of the rows of B. Thus, for each j 1, . . . , m, the jth row A j Bof the matrix product AB is a linear combination of the rows of B, with coefficientstaken from the jth row of A.1.2.2 Systems of linear equationsMotivated by Viewpoint 3 concerning matrix multiplication—in particular, thatAx x1 A1 x2 A2 · · · xn An ,where A1 , . . . , An are the columns of a matrix A and x (x1 , . . . , xn ) Rn —we make thefollowing definition.hiDefinition 4: Suppose A A1 A2 · · · An , where each submatrix A j consists of a single column (so A has n columns in all). The set of all possible linearcombinations of these columns (also known as span({A1 , . . . , An })){c1 A1 c2 A2 · · · cn An c1 , c2 , . . . , cn R} ,is called the column space of A. We use the symbol col(A) to denote the columnspace.14

1.2 Matrix Multiplication and Systems of Linear EquationsThe most common problem in linear algebra (and the one we seek in this course tounderstand most completely) is the one of solving m linear equationsa11 x1 a12 x2 . . . a1n xna21 x1 a22 x2 . . . a2n xn. b1b2.(1.2)am1 x1 am2 x2 . . . amn xn bmin the n unknowns x1 , . . . , xn . If one uses the coefficients and unknowns to build acoefficient matrix and vectors b1 x1 a11 a12 · · · a1n b2 x2 a21 a22 · · · a2n andb . ,A . , x . . . . ···. bnxnam1 am2 · · · amnthen by our definitions of matrix equality and multiplication, the system (1.2) may beexpressed more concisely as the matrix equationAx b ,(1.3)where the vector b is known and x is to be found. Given Viewpoint 3 for conceptualizingmatrix multiplication above, problem (1.3) really presents two questions to be answered:(I) Is b in the column space of A (i.e., is (1.3) solvable)?(II) If it is, then what are the possible n-tuples x (x1 , . . . , xn ) of coefficients so that thelinear combinationx1 A1 x2 A2 · · · xn Anof the columns of A equals b?When the number m of equations and the number n of unknowns in system (1.2) areequal, it is often the case that there is one unique answer for each of the variables xi (or,equivalently, one unique vector x satisfying (1.3). Our main goal in the linear algebracomponent of this course is to understand completely when (1.3) is and is not solvable,how to characterize solutions when it is, and what to do when it is not.One special instance of the case m n is when A is nonsingular. In this case, if A 1 isknown, then the answer to question (I) is an immediate “yes”. Moreover, one may obtainthe (unique) solution of (1.3) (thus answering question (II)) via left-multiplication by A 1 :Ax b A 1 Ax A 1 b Ix A 1 b x A 1 b .15

1 Solving Linear Systems of EquationsImportant Note: One should not think about the previous matrix-algebraicsteps in terms of dividing by a matrix (and it is complete nonsense to talkabout dividing by a vector!). One speaks, instead, of multiplying by the inversematrix, when that exists. It is, moreover, extremely important to pay attentionto which side of an expression you wish to multiply by that inverse. Oftenplacing it on the wrong side yields a nonsensical mathematical expression!In practical settings, however, A 1 must first be found (if, indeed, it exists!) before we canuse it to solve the matrix problem. Despite the availability of the matrix method inverse()in Sage, finding the inverse of a matrix is a very inefficient thing to do computationally,and quite impossible when A 1 does not exist. In the Section 1.4 we will look at Gaussianelimination as a procedure for solving linear systems of equations. Gaussian eliminationserves as a foundation for the LU-factorization, which supplies us with a comprehensivemethod for solving Ax b whenever the matrix problem can be solved (even in caseswhere A 1 does not exist).1.3 Affine transformations of R2Suppose A is an m-by-n matrix. When we left-multiply a vector v Rn by such a matrixA, the result is a vector Av Rm . In this section we will focus upon functions which takeinputs v Rn and produce outputs Av Rm . A function such as this could be givena name, but we will generally avoid doing so, referring to it as “the function v 7 Av”.When we wish to be explicit about the type of objects the input and output are, we mightwrite “(v 7 Av) : Rn Rm ”, which points out that the function v 7 Av maps objectsfrom Rn (inputs) to objects from Rm (outputs). But if the reader is informed that A is anm-by-n matrix, he should already be aware that inputs/outputs to and from the functionv 7 Av are in Rn and Rm respectively.In this subsection A will be understood to be a 2-by-2 matrix. Assuming this, it is thecase that (v 7 Av) : R2 R2 . We wish to focus our attention on the action of such afunction on the entire plane of vectors for various types of 2-by-2 matrices A.1. Rotations of the plane. Our first special family of matrices are those of the form"#cos α sin αA ,sin α cos α(1.4)for α R. We know that points in the plane may be specified using polar coordinates,so any vector v R2 may be expressed as v (r cos θ, r sin θ), where (r, θ) is a polarrepresentation of the terminal point of v. To the see the action of A on a typical v,16

1.3 Affine transformations of R2note that"#"#"#cos α sin α r cos θcos α cos θ sin α sin θAv rsin α cos α r sin θsin α cos θ cos α sin θ"#r cos(α θ) .r sin(α θ)where we have employed several angle sum formulas2 in the last equality. Thatis, for an input vector v with terminal point (r, θ), the output Av is a vector withterminal point (r, α θ). The output is the same distance r from the origin as theinput, but has been rotated about the origin through an angle α. Thus, for matricesof the form (1.4), the function v 7 Av rotates the entire plane counterclockwise (forpositive α) about the origin through an angle α. Of course, the inverse matrix wouldreverse this process, and hence it must be" 1A#"#cos( α) sin( α)cos(α) sin(α) .sin( α) cos( α) sin(α) cos(α)2. Reflections across a line containing the origin.First notice that, when"#1 0A ,0 1then"#" #"#1 0 v1v1Av .0 1 v2 v2Thus, for this special matrix A, v 7 Av maps points in the plane to their reflectionsthrough the x-axis.Now let u (cos θ, sin θ) (i.e., u is a unit vector). Every line in the plane containingthe origin may be expressed as a one-parameter family L {tu t R} of multiplesof u where θ has been chosen (fixed

1 Solving Linear Systems of Equations 1.1 Matrix Algebra Definition 1: An m-by-n real matrix is a table of m rows and n columns of real numbers. We say that the matrix has dimensions m-by-n. The plural of matrix is matrices. Remarks: 1.Often we write a matrix A (a ij), indicating that the matrix under consideration may be refer