(*^ ::[ Information = "This is a Mathematica Notebook file. It contains ASCII text, and can be transferred by email, ftp, or other text-file transfer utility. It should be read or edited using a copy of Mathematica or MathReader. If you received this as email, use your mail application or copy/paste to save everything from the line containing (*^ down to the line containing ^*) into a plain text file. On some systems you may have to give the file a name ending with ".ma" to allow Mathematica to recognize it as a Notebook. The line below identifies what version of Mathematica created this file, but it can be opened using any other version as well."; FrontEndVersion = "NeXT Mathematica Notebook Front End Version 2.2"; NeXTStandardFontEncoding; fontset = title, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, L1, e8, 24, "Times"; ; fontset = subtitle, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, L1, e6, 18, "Times"; ; fontset = subsubtitle, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, italic, L1, e6, 14, "Times"; ; fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, grayBox, M22, bold, L1, a20, 18, "Times"; ; fontset = subsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, blackBox, M19, bold, L1, a15, 14, "Times"; ; fontset = subsubsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, whiteBox, M18, bold, L1, a12, 12, "Times"; ; fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 10, "Times"; ; fontset = input, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeInput, M42, N23, bold, L1, 12, "Courier"; ; fontset = output, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, "Courier"; ; fontset = message, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L1, 12, "Courier"; ; fontset = print, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L1, 12, "Courier"; ; fontset = info, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L1, 12, "Courier"; ; fontset = postscript, PostScript, formatAsPostScript, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeGraphics, M7, l34, w282, h287, L1, 12, "Courier"; ; fontset = name, inactive, noPageBreakInGroup, nohscroll, preserveAspect, M7, italic, B65535, L1, 10, "Times"; ; fontset = header, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, italic, L1, 12, "Times"; ; fontset = leftheader, 12; fontset = footer, inactive, nohscroll, noKeepOnOnePage, preserveAspect, center, M7, italic, L1, 12, "Times"; ; fontset = leftfooter, 12; fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = completions, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12, "Courier"; ; fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; paletteColors = 128; currentKernel; ] :[font = input; Cclosed; preserveAspect; center; startGroup] Rank of Matrices and Linear Systems ;[s] 1:0,0;35,-1; 1:1,21,16,Times,1,24,0,0,0; :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Matrices, Reduced Forms, and Solutions of Linear Systems :[font = text; inactive; preserveAspect] DEFINITION: A matrix R is said to be in row echelon form if (1) The nonzero rows of R precede the zero rows. (2) The column numbers of the leading entries of the nonzero rows of R , say rows 1, 2, ... r, form an increasing sequence of numbers c1 < c2 < .... < cr . (3) Each leading entry of R has only zeros below it. The matrix R is in reduced row echelon form if, in addition to the above, (4) Each leading entry of R is 1. (5) Each leading entry of R has only zeros above it. Gaussian Elimination has the goal of reaching row echelon form, then backsolving. But Gauss -Jordan Elimination has the goal of reaching reduced row echelon form. One of the differences between the forms is that a matrix can have more than one row reduced form. But it is a remarkable fact that every matrix has one and only one row echelon form. That is the content of the following KEY FACT: Every matrix can be reduced by a sequence of elementary row operations to ONE AND ONLY ONE reduced row echelon form. Once we have this fact, we can define the very useful idea of rank of a matrix: ;[s] 17:0,0;44,1;60,2;266,3;267,4;271,5;272,6;283,7;284,8;348,9;372,10;396,11;429,12;532,13;552,14;621,15;646,16;1161,-1; 17:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,10,8,Times,66,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = text; inactive; preserveAspect] DEFINITION: The rank of a matrix is the number of nonzero rows in the Row Echelon Form of the matrix. This number is written as rank(A). Here is a simple fact that we can deduce right away from this definition: FACT: Let A be an m´n matrix. Then rank(A) £ Min[ m, n]. Mathematica will find the Row Echelon Form for us automatically, from which we can read off the rank of A: ;[s] 9:0,0;18,1;22,2;270,3;271,4;298,5;299,6;315,7;326,8;423,-1; 9:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; preserveAspect] a = {{1,1,2},{2,2,5},{3,3,7}} :[font = input; preserveAspect] MatrixForm[a] :[font = input; preserveAspect] r = RowReduce[a] :[font = input; preserveAspect] MatrixForm[r] :[font = text; inactive; preserveAspect] Try substituting some different matrices for the matrix a in the above cell. In particular, build a 5´3 matrix and calcualte its Row Echelon Form and rank. ;[s] 3:0,0;105,1;106,2;161,-1; 3:1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = text; inactive; preserveAspect] Actually, we have seen from earlier discussion that the following key fact is true: KEY FACT: The linear system (LS) with coefficient matrix A and right hand side vector b is consistent iff rank A = rank [A | b], in which case either: (1) rank A = n (number of unknowns of (LS)), in which case (LS) has a unique solution, or (2) rank A < n, in which case (LS) has an infinite number of solutions. REMARK: Note the consistency condition simply says that the system is consistent exactly when no pivot occurs in the last column of the augmented matrix. Moreover, if the system is consistent, n - rank A is exactly the number of free variables of the system, so that (1) and (2) say that there is a unique solution when there are no free variables, and infinitely many solutions otherwise. Let's see how Mathematica will handle the system with coefficient matrix and right hand side as follows: ;[s] 3:0,0;851,1;862,2;943,-1; 3:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; preserveAspect] a = {{1,1,1},{2,2,4},{0,0,1}} :[font = input; preserveAspect] b = {2,8,2} :[font = input; preserveAspect] LinearSolve[a,b] :[font = text; inactive; preserveAspect] Conclusion? Get another view of things by doing the Row Echelon Form of the augmented matrix. Click on the next two cells: :[font = input; preserveAspect] aa={{1,1,1,2},{2,2,4,8},{0,0,1,2}} :[font = input; preserveAspect] MatrixForm[aa] :[font = input; preserveAspect] MatrixForm[RowReduce[aa]] :[font = text; inactive; preserveAspect] Try LinearSolve on the following example (also from the lecture): :[font = input; preserveAspect] a = {{1,1,1},{1,1,2},{1,1,0}} :[font = input; preserveAspect] b = {2,4,2} :[font = input; preserveAspect; endGroup] LinearSolve[a,b] :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Exercise :[font = text; inactive; preserveAspect; endGroup; endGroup] Determine the solvability of the following systems using (a) the row echelon form and (b) a direct Mathematica function: 1) 5 x + 3 y - 4 z = 0 x - y + z = 5 3 x + 2 y + 9 z = -1 2) x + 2 y + 3 z = 4 4 x + 5 y + 6 z = 7 7 x + 8 y + 9 z = 10 x - y + z = 0 3) 6 a + 5 b - c = 5 a + 2 b + 3 c = 5 3 a - b - 10 c = -8 ;[s] 3:0,0;100,1;111,2;460,-1; 3:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; ^*)