(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 4.0, MathReader 4.0, or any compatible application. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. ***********************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 18562, 556]*) (*NotebookOutlinePosition[ 19416, 586]*) (* CellTagsIndexPosition[ 19372, 582]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell[TextData[StyleBox["Determinants", FontFamily->"Times", FontSize->24]], "Input", TextAlignment->Center, ImageRegion->{{-0, 1}, {0, 1}}], Cell[BoxData[ StyleBox[\(Author : Thomas\ Shores\[IndentingNewLine] University\ of\ Nebraska\[IndentingNewLine] Send\ comments\ \(to : tshores@math . unl . edu\)\), FontWeight->"Plain", FontSlant->"Plain", FontTracking->"Plain", FontVariations->{"Underline"->False, "Outline"->False, "Shadow"->False, "StrikeThrough"->False, "Masked"->False, "CompatibilityType"->0, "RotationAngle"->0}]], "Input"], Cell[CellGroupData[{ Cell["Definition and Basic Properties", "Subsection", ImageRegion->{{0, 1}, {0, 1}}], Cell[TextData[{ "The main reason that determinants are useful is the following: for a \ given matrix A they provide us with a single number (called the ", StyleBox["determinant", FontSlant->"Italic"], " ", StyleBox["of", FontSlant->"Italic"], " ", StyleBox["A", FontSlant->"Italic"], "), which is nonzero precisely when A is an invertible matrix.\n\nHere 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. \n\nDEFINITION. The determinant \ of a 1", "\[Cross]", "1 matrix is the single entry of the matrix. For n > 1, \n \ the determinant of the n", "\[Cross]", "n matrix A = [a", StyleBox["i,j", FontVariations->{"CompatibilityType"->"Subscript"}], "] is the Sum[a", StyleBox["i,1", FontVariations->{"CompatibilityType"->"Subscript"}], " A", StyleBox["i,1", FontVariations->{"CompatibilityType"->"Subscript"}], "], where A", StyleBox["i,j ", FontVariations->{"CompatibilityType"->"Subscript"}], "means the \n (i,j)", StyleBox["th", FontSlant->"Italic"], " cofactor, i.e., (-1)", StyleBox["i+j", FontVariations->{"CompatibilityType"->"Superscript"}], " M", StyleBox["i,j", FontVariations->{"CompatibilityType"->"Subscript"}], ", where M", StyleBox["i,j", FontVariations->{"CompatibilityType"->"Subscript"}], " is the (i,j)", StyleBox["th", FontSlant->"Italic"], " minor of A, i.e., the \n determinant of the matrix obtained from \ A by deleting the ith row and jth column of A\n and collapsing the \ remaining elements together. We use the notations |A| or det(A)\n \ for the determinant of the matrix A. \n\nNB: There are two important \ things to remember about determinants:\n\t(1) Spelling: it is spelled \ determinANT.\n\t(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.\n\nWe'll need these definitions for D12-D14:\n\nDEFINITION. \ The ", StyleBox["minors matrix", FontSlant->"Italic"], " of the matrix A = [a", StyleBox["i,j", FontVariations->{"CompatibilityType"->"Subscript"}], "] is the matrix M(A) = [M", StyleBox["i,j", FontVariations->{"CompatibilityType"->"Subscript"}], "(A)] of\n minors of A.\nDEFINITION. The ", StyleBox["cofactors matrix", FontSlant->"Italic"], " of a matrix A = [a", StyleBox["i,j", FontVariations->{"CompatibilityType"->"Subscript"}], "] is the matrix A", StyleBox["cof", FontVariations->{"CompatibilityType"->"Subscript"}], " = [A", StyleBox["i,j", FontVariations->{"CompatibilityType"->"Subscript"}], "] of \n cofactors of the matrix A.\n\nHere are the basic laws of \ determinants, all of which can be deduced from the definition:\n\nD1: The \ determinant of a matrix with a zero row is 0.\nD2: Exchanging two rows of a \ determinant changes its sign.\nD3: 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.\nD4: A determinant with repeated rows \ has value 0.\nD5: The determinant is linear in each row.\nD6: Adding a \ multiple of one row to another does not change a determinant.\nD7: The \ determinant of an (upper) triangular matrix is the product of the diagonal \ elements.\nD8: The determinant of a matrix is nonzero if and only if the \ matrix is nonsingular.\nD9: The determinant of a product of matrices is the \ product of the determinants.\nD10: The determinant of a matrix is the same \ as the determinant of its transpose.\nD11: The determinant of a matrix can \ be computed by expanding cofactors along any row or column of the matrix.\n\ D12: For any (square) matrix A, |A| adj(A) = adj(A) |A| = |A| I\nD13: If \ |A| is not 0, then the inverse of A is given by Inv(A) = (", StyleBox["1", FontVariations->{"CompatibilityType"->"Superscript"}], "/", StyleBox["|A|", FontVariations->{"CompatibilityType"->"Subscript"}], ") adj(A).\nD14: (Cramer's Rule) If |A| is not 0, then the unique \ solution to A . x = b is given by x", StyleBox["j", FontVariations->{"CompatibilityType"->"Subscript"}], " = ", StyleBox["|Aj|", FontVariations->{"CompatibilityType"->"Superscript"}], " / ", StyleBox["|A|", FontVariations->{"CompatibilityType"->"Subscript"}], ", where |A", StyleBox["j", FontVariations->{"CompatibilityType"->"Subscript"}], "| is the determinant of the matrix obtained from A by replacing the ", StyleBox["jth", FontSlant->"Italic"], " column of A by b." }], "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Here are some examples to verify some of the laws D1-D11...", "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["a = {{ 1, 2},{-3 ,4 }}", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["b = {{1 ,2 },{2 ,3 }}", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Det[a]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Det[b]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Det[a+b]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Det[{{1,2,3},{0,4,5},{0,0,6}}]", "Input", ImageRegion->{{-0, 1}, {0, 1}}] }, Open ]], Cell[CellGroupData[{ Cell["Adjoints, Inverses, and Solution of Linear Systems", "Subsection", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Now for some illustrations of D12-D13:", "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["A = {{1,3,2},{2,1,1},{1,0,1}}", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["\<\ Just in case you prefer a more \[OpenCurlyDoubleQuote]matrix-like\ \[CloseCurlyDoubleQuote] appearance in the output, activate this cell:\ \>", \ "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["MatrixForm[A]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ "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 ", StyleBox["Mathematica", FontSlant->"Italic"], ", but I want you to figure it out)." }], "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["MinA = {{ , , }, { , , }, { , , }}", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["\<\ 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 \ \[OpenCurlyDoubleQuote]checkerboard\[CloseCurlyDoubleQuote] of +/- 's. So do \ the following:\ \>", "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["plusminus = {{1,-1,1},{-1,1,-1},{1,-1,1}}", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ "Now to do the overlaying, multiply corresponding entries of the matrix ", StyleBox["plusminus", FontSlant->"Italic"], " and A by doing the following (which, by the way, is why * won't give real \ matrix multiplication):" }], "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Acof = plusminus * MinA", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Do the following cell:", "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["adjA = Transpose[Acof]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Now for the magic... Activate the following:", "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["A . adjA", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["adjA . A", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["detA = Det[A]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["\<\ This can't be a coincidence. It isn't !!! Test this out::\ \>", "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Inverse[A]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["(1/Det[A]) adjA", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["\<\ We have already seen a special case of D13, namely the 2\[Cross]2 \ case. For consider the matrix below and its inverse:\ \>", "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["m = {{a,b},{c,d}}", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["MatrixForm[m]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Invm = Inverse[m]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["MatrixForm[Invm]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ "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\n \n x = (", StyleBox["1", FontVariations->{"CompatibilityType"->"Superscript"}], " / ", StyleBox["|A|", FontVariations->{"CompatibilityType"->"Subscript"}], " ) adj(A) b.\n \n If we were to pick \ this expression apart for each coordinate of x we would arrive at the famous \ Cramer's Rule (D14)." }], "Text", ImageRegion->{{-0, 1}, {0, 1}}] }, Closed]], Cell[CellGroupData[{ Cell["Determinant Solutions v s. Gaussian eliminations", "Subsection", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ " 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", "\[Cross]", "n system. This is vast compared to the number n", StyleBox["3", FontVariations->{"CompatibilityType"->"Superscript"}], " flops required for Gaussian elimination. (If you haven't seen the term \ before, a \[OpenCurlyDoubleQuote]flop\[CloseCurlyDoubleQuote] 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 ", StyleBox["n", FontSlant->"Italic"], " to another requires ", StyleBox["n", FontSlant->"Italic"], " flops.)\n \n 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 n", StyleBox["3", FontVariations->{"CompatibilityType"->"Superscript"}], " /", StyleBox["3", FontVariations->{"CompatibilityType"->"Subscript"}], " 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 ", StyleBox["n", FontSlant->"Italic"], " 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.\n 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", "\[Cross]", "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 ", StyleBox["Mathematica. ", FontSlant->"Italic"], "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." }], "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["a = Table[i+j,{i,10},{j,10}]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["b = Table[1,{i,10}]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["11 * Timing[Det[a]]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["Timing[LinearSolve[a,b]]", "Input", ImageRegion->{{-0, 1}, {0, 1}}] }, Closed]], Cell[CellGroupData[{ Cell["Exercises", "Subsection", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[StyleBox["For the following exercises, use the matrices :", FontFamily->"Times", FontWeight->"Plain"]], "Input", CellMargins->{{13, Inherited}, {Inherited, Inherited}}, ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ StyleBox[" ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e6", FontWeight->"Plain"], StyleBox["1 3 0 5 4", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f6", FontWeight->"Plain"], StyleBox[" ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e6", FontWeight->"Plain"], StyleBox["2 2 0 -5 7", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f6", FontWeight->"Plain"], StyleBox["\n ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e7", FontWeight->"Plain"], StyleBox["0 8 3 -5 2", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f7", FontWeight->"Plain"], StyleBox[" ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e7", FontWeight->"Plain"], StyleBox["1 9 6 -3 8", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f7", FontWeight->"Plain"], StyleBox["\nA = ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f7", FontWeight->"Plain"], StyleBox["5 -5 2 -1 0", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f7", FontWeight->"Plain"], StyleBox[" B = ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f7", FontWeight->"Plain"], StyleBox[" 8 -7 0 2 1 ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e7", FontWeight->"Plain"], StyleBox["\n ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e7", FontWeight->"Plain"], StyleBox["2 1 -4 7 9", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f7", FontWeight->"Plain"], StyleBox[" ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e7", FontWeight->"Plain"], StyleBox["4 -6 -2 1 7 ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e7", FontWeight->"Plain"], StyleBox["\n ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e8", FontWeight->"Plain"], StyleBox["6 -8 0 1 0", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f8", FontWeight->"Plain"], StyleBox[" ", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2e8", FontWeight->"Plain"], StyleBox["5 0 -9 9 0", FontFamily->"Helvetica", FontWeight->"Plain"], StyleBox["\:f2f8", FontWeight->"Plain"] }], "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ StyleBox["Evaluate :\n Det A\n Det B\n Det (A + B)\n Det (2 A) \ Write this in terms of Det (A) and verify using ", FontFamily->"Times", FontWeight->"Plain"], StyleBox["Mathematica", FontFamily->"Times", FontWeight->"Plain", FontSlant->"Italic"], StyleBox[".\n Det (A", FontFamily->"Times", FontWeight->"Plain"], StyleBox["3", FontFamily->"Times", FontWeight->"Plain", FontVariations->{"CompatibilityType"->"Superscript"}], StyleBox[") Write this in terms of Det (A) and verify using ", FontFamily->"Times", FontWeight->"Plain"], StyleBox["Mathematica", FontFamily->"Times", FontWeight->"Plain", FontSlant->"Italic"], StyleBox[".\n Det (A B)", FontFamily->"Times", FontWeight->"Plain"] }], "Input", CellMargins->{{12, Inherited}, {Inherited, Inherited}}, ImageRegion->{{-0, 1}, {0, 1}}] }, Closed]] }, Closed]] }, FrontEndVersion->"4.0 for X", ScreenRectangle->{{0, 1152}, {0, 864}}, WindowToolbars->{}, CellGrouping->Manual, WindowSize->{520, 600}, WindowMargins->{{Automatic, 308}, {104, Automatic}}, PrivateNotebookOptions->{"ColorPalette"->{RGBColor, -1}}, ShowCellLabel->True, ShowCellTags->False, RenderingOptions->{"ObjectDithering"->True, "RasterDithering"->False} ] (*********************************************************************** Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. ***********************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1739, 51, 147, 4, 40, "Input"], Cell[1889, 57, 473, 13, 59, "Input"], Cell[CellGroupData[{ Cell[2387, 74, 86, 1, 45, "Subsection"], Cell[2476, 77, 4838, 115, 1024, "Text"], Cell[7317, 194, 109, 1, 32, "Text"], Cell[7429, 197, 73, 1, 27, "Input"], Cell[7505, 200, 72, 1, 27, "Input"], Cell[7580, 203, 57, 1, 27, "Input"], Cell[7640, 206, 57, 1, 27, "Input"], Cell[7700, 209, 59, 1, 27, "Input"], Cell[7762, 212, 81, 1, 27, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[7880, 218, 106, 1, 29, "Subsection"], Cell[7989, 221, 88, 1, 70, "Text"], Cell[8080, 224, 80, 1, 70, "Input"], Cell[8163, 227, 198, 5, 70, "Text"], Cell[8364, 234, 64, 1, 70, "Input"], Cell[8431, 237, 299, 7, 70, "Text"], Cell[8733, 246, 94, 1, 70, "Input"], Cell[8830, 249, 278, 6, 70, "Text"], Cell[9111, 257, 92, 1, 70, "Input"], Cell[9206, 260, 294, 7, 70, "Text"], Cell[9503, 269, 74, 1, 70, "Input"], Cell[9580, 272, 72, 1, 70, "Text"], Cell[9655, 275, 73, 1, 70, "Input"], Cell[9731, 278, 94, 1, 70, "Text"], Cell[9828, 281, 59, 1, 70, "Input"], Cell[9890, 284, 59, 1, 70, "Input"], Cell[9952, 287, 64, 1, 70, "Input"], Cell[10019, 290, 117, 4, 70, "Text"], Cell[10139, 296, 61, 1, 70, "Input"], Cell[10203, 299, 66, 1, 70, "Input"], Cell[10272, 302, 179, 4, 70, "Text"], Cell[10454, 308, 68, 1, 70, "Input"], Cell[10525, 311, 64, 1, 70, "Input"], Cell[10592, 314, 68, 1, 70, "Input"], Cell[10663, 317, 67, 1, 70, "Input"], Cell[10733, 320, 635, 13, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[11405, 338, 105, 1, 29, "Subsection"], Cell[11513, 341, 2724, 53, 70, "Text"], Cell[14240, 396, 79, 1, 70, "Input"], Cell[14322, 399, 70, 1, 70, "Input"], Cell[14395, 402, 70, 1, 70, "Input"], Cell[14468, 405, 75, 1, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[14580, 411, 65, 1, 29, "Subsection"], Cell[14648, 414, 222, 4, 70, "Input"], Cell[14873, 420, 2739, 102, 70, "Input"], Cell[17615, 524, 919, 28, 70, "Input"] }, Closed]] }, Closed]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)