(*^
::[ 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;
^*)