(*^ ::[ 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] Determinants ;[s] 1:0,0;12,-1; 1:1,21,16,Times,1,24,0,0,0; :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Definition and Basic Properties :[font = text; inactive; preserveAspect] The main reason that determinants are useful is the following: for a given matrix A they provide us with a single number (called the determinant of A), which is nonzero precisely when A is an invertible matrix. Here is a summary of all the laws of determinants that we need. An example of each law will be given below. Let's start with the definition of determinant in terms of expansion down the first column. DEFINITION. The determinant of a 1´1 matrix is the single entry of the matrix. For n > 1, the determinant of the n´n matrix A = [ai,j] is the Sum[ai,1 Ai,1], where Ai,j means the (i,j)th cofactor, i.e., (-1)i+j Mi,j, where Mi,j is the (i,j)th minor of A, i.e., the determinant of the matrix obtained from A by deleting the ith row and jth column of A and collapsing the remaining elements together. We use the notations |A| or det(A) for the determinant of the matrix A. NB: There are two important things to remember about determinants: (1) Spelling: it is spelled determinANT. (2) What it is: a determinant is a NUMBER, not a matrix or vector. Also, one calculates the determinant of a SQUARE matrix to get the resulting number. We'll need these definitions for D12-D14: DEFINITION. The minors matrix of the matrix A = [ai,j] is the matrix M(A) = [Mi,j(A)] of minors of A. DEFINITION. The cofactors matrix of a matrix A = [ai,j] is the matrix Acof = [Ai,j] of cofactors of the matrix A. Here are the basic laws of determinants, all of which can be deduced from the definition: D1: The determinant of a matrix with a zero row is 0. D2: Exchanging two rows of a determinant changes its sign. D3: Multiplying a single row of a matrix by a constant gives a determinant whose value is the constant times the determinant of the original matrix. D4: A determinant with repeated rows has value 0. D5: The determinant is linear in each row. D6: Adding a multiple of one row to another does not change a determinant. D7: The determinant of an (upper) triangular matrix is the product of the diagonal elements. D8: The determinant of a matrix is nonzero if and only if the matrix is nonsingular. D9: The determinant of a product of matrices is the product of the determinants. D10: The determinant of a matrix is the same as the determinant of its transpose. D11: The determinant of a matrix can be computed by expanding cofactors along any row or column of the matrix. D12: For any (square) matrix A, |A| adj(A) = adj(A) |A| = |A| I D13: If |A| is not 0, then the inverse of A is given by Inv(A) = (1/|A|) adj(A). D14: (Cramer's Rule) If |A| is not 0, then the unique solution to A . x = b is given by xj = |Aj| / |A|, where |Aj| is the determinant of the matrix obtained from A by replacing the jth column of A by b. ;[s] 57:0,0;134,1;145,2;146,3;148,4;149,5;150,6;455,7;456,8;551,9;552,10;567,11;570,12;584,13;587,14;589,15;592,16;602,17;606,18;631,19;633,20;654,21;657,22;659,23;662,24;671,25;674,26;687,27;689,28;1287,29;1300,30;1321,31;1324,32;1349,33;1352,34;1398,35;1414,36;1433,37;1436,38;1454,39;1457,40;1462,41;1465,42;2626,43;2627,44;2628,45;2631,46;2733,47;2734,48;2737,49;2741,50;2744,51;2747,52;2758,53;2759,54;2828,55;2831,56;2900,-1; 57: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;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,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,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,32,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,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;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,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,32,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,32,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,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = text; inactive; preserveAspect] Here are some examples to verify some of the laws D1-D11... :[font = input; preserveAspect] a = {{ 1, 2},{-3 ,4 }} :[font = input; preserveAspect] b = {{1 ,2 },{2 ,3 }} :[font = input; preserveAspect] Det[a] :[font = input; preserveAspect] Det[b] :[font = input; preserveAspect] Det[a+b] :[font = input; preserveAspect; endGroup] Det[{{1,2,3},{0,4,5},{0,0,6}}] :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Adjoints, Inverses, and Solution of Linear Systems :[font = text; inactive; preserveAspect] Now for some illustrations of D12-D13: :[font = input; preserveAspect] A = {{1,3,2},{2,1,1},{1,0,1}} :[font = text; inactive; preserveAspect] Just in case you prefer a more ªmatrix-likeº appearance in the output, activate this cell: :[font = input; preserveAspect] MatrixForm[A] :[font = text; inactive; preserveAspect] O.K., now let's get down to business. Eyeball the last output and fill in the matrix of cofactors of A (yes, there is a way to do it in Mathematica, but I want you to figure it out). ;[s] 3:0,0;137,1;148,2;185,-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] MinA = {{ , , }, { , , }, { , , }} :[font = text; inactive; preserveAspect] All you have to do to convert the matrix of minors into the matrix of cofactors is to overlay the entries of M(A) with a ªcheckerboardº of +/- 's. So do the following: :[font = input; preserveAspect] plusminus = {{1,-1,1},{-1,1,-1},{1,-1,1}} :[font = text; inactive; preserveAspect] Now to do the overlaying, multiply corresponding entries of the matrix plusminus and A by doing the following (which, by the way, is why * won't give real matrix multiplication): ;[s] 3:0,0;72,1;81,2;179,-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] Acof = plusminus * MinA :[font = text; inactive; preserveAspect] Do the following cell: :[font = input; preserveAspect] adjA = Transpose[Acof] :[font = text; inactive; preserveAspect] Now for the magic... Activate the following: :[font = input; preserveAspect] A . adjA :[font = input; preserveAspect] adjA . A :[font = input; preserveAspect] detA = Det[A] :[font = text; inactive; preserveAspect] This can't be a coincidence. It isn't !!! Test this out:: :[font = input; preserveAspect] Inverse[A] :[font = input; preserveAspect] (1/Det[A]) adjA :[font = text; inactive; preserveAspect] We have already seen a special case of D13, namely the 2´2 case. For consider the matrix below and its inverse: ;[s] 3:0,0;56,1;57,2;113,-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 = input; preserveAspect] m = {{a,b},{c,d}} :[font = input; preserveAspect] MatrixForm[m] :[font = input; preserveAspect] Invm = Inverse[m] :[font = input; preserveAspect] MatrixForm[Invm] :[font = text; inactive; preserveAspect; endGroup] One final fact:: we now have an explicit formula for the unique solution x of A x = b, namely, from the formula x = Inv(A) b and D14, we get (in the case |A| is not 0) that x = (1 / |A| ) adj(A) b. If we were to pick this expression apart for each coordinate of x we would arrive at the famous Cramer's Rule (D14). ;[s] 5:0,0;222,1;223,2;226,3;229,4;400,-1; 5:1,11,8,Times,0,12,0,0,0;1,11,8,Times,32,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; :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Determinant Solutions v s. Gaussian eliminations :[font = text; inactive; preserveAspect] The truth of the matter is that Cramer's Rule and adjoints are only good for small matrices and theoretical arguments. For if you evaluate determinants in a straightforward way from the definition, the work in doing so is about n! flops for an n´n system. This is vast compared to the number n3 flops required for Gaussian elimination. (If you haven't seen the term before, a ªflopº in numerical linear algebra is a single addition or subtraction, together with a single multiplication or division, and a bit of index fiddling. One rounds up if only one operation is present. For example, it is not hard to show that the operation of adding a multiple of one row vector of length n to another requires n flops.) On the other hand, there is a sneaky way to evaluate determinants that is much less work than the definition: use elementary row operations together with D2 , D6 and the elementary operations that correspond to these rules to reduce the determinant to that of a triangular matrix. This will only require about n3 /3 flops. As a matter of fact, it is tantamount to Gaussian elimination. But to use Cramer's Rule, you will have to calculate (n + 1) determinants. So why bother with Cramer's Rule on larger problems when it still will take about n times as much work as Gaussian elimination? A similar remark applies to computing adjoints instead of using Gauss -Jordan elimination on the super-augmented matrix of A. In case you're not convinced, try the following: let's make Mathematica do a reasonable problem. First we will simulate Cramer's Rule on a 10´10 by doing 11 determinants. Then we compare to a direct LinearSolve. Incidentally, Mathematica really uses elementary row operations to compute a determinant. One could make a definition that does determinants from definition by recursion. It would take much longer than the built-in function Det of Mathematica. In each of the timing cells below, be sure to click on each cell twice. You will get different numbers. This has to do with having or not having data and programs in memory. ;[s] 19:0,0;251,1;252,2;300,3;301,4;692,5;693,6;715,7;716,8;1045,9;1046,10;1048,11;1049,12;1283,13;1284,14;1600,15;1601,16;1905,17;1920,18;2097,-1; 19: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,11,8,Times,32,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;1,11,8,Times,32,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,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,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; preserveAspect] a = Table[i+j,{i,10},{j,10}] :[font = input; preserveAspect] b = Table[1,{i,10}] :[font = input; preserveAspect] 11 * Timing[Det[a]] :[font = input; preserveAspect; endGroup] Timing[LinearSolve[a,b]] :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Exercises :[font = input; preserveAspect; leftWrapOffset = 13] For the following exercises, use the matrices : ;[s] 1:0,0;47,-1; 1:1,11,8,Times,0,12,0,0,0; :[font = input; preserveAspect] æ1 3 0 5 4ö æ2 2 0 -5 7ö ç0 8 3 -5 2÷ ç1 9 6 -3 8÷ A = ÷5 -5 2 -1 0÷ B = ÷ 8 -7 0 2 1 ç ç2 1 -4 7 9÷ ç4 -6 -2 1 7 ç è6 -8 0 1 0ø è5 0 -9 9 0ø ;[s] 40:0,0;9,1;10,2;30,3;31,4;46,5;47,6;70,7;71,8;81,9;82,10;102,11;103,12;118,13;119,14;142,15;143,16;150,17;151,18;171,19;172,20;184,21;185,22;209,23;210,24;220,25;221,26;241,27;242,28;257,29;258,30;281,31;282,32;292,33;293,34;313,35;314,36;329,37;330,38;353,39;354,-1; 40:1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,9,Helvetica,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0; :[font = input; preserveAspect; leftWrapOffset = 12; endGroup; endGroup] Evaluate : Det A Det B Det (A + B) Det (2 A) Write this in terms of Det (A) and verify using Mathematica. Det (A3) Write this in terms of Det (A) and verify using Mathematica. Det (A B) ;[s] 7:0,0;115,1;126,2;138,3;139,4;196,5;207,6;223,-1; 7: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,32,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; ^*)