{"id":231,"date":"2019-09-10T18:23:32","date_gmt":"2019-09-10T18:23:32","guid":{"rendered":"http:\/\/104.42.120.246.xip.io\/calculus-tutorials\/?page_id=231"},"modified":"2020-06-18T16:56:21","modified_gmt":"2020-06-18T16:56:21","slug":"solving-systems-of-equations","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/calculus\/hmc-mathematics-calculus-online-tutorials\/linear-algebra\/solving-systems-of-equations\/","title":{"rendered":"Solving Systems of Equations"},"content":{"rendered":"\n<script type=\"text\/x-mathjax-config\">\n  MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], [\"\\(\",\"\\)\"]] } });\n<\/script>\n\n\n\n<script type=\"text\/javascript\" src=\"http:\/\/cdn.mathjax.org\/mathjax\/latest\/MathJax.js?config=TeX-AMS_HTML\">\n<\/script>\n\n\n\n<meta http-equiv=\"X-UA-Compatible\" content=\"IE=EmulateIE7\">\n\n\n\n<title>Solving Systems of Linear Equations; Row Reduction &#8211; HMC Calculus Tutorial<\/title>\n\n\n\n<p>\n<!------------------------>\n\n<!--The following three lines are necessary in order to display augmented matrices, using the \\Matrix\n\tenvironment wihin math mode-->\n$\\def\\Height{\\vphantom{\\begin{array}{c}a\\cr a\\cr a\\cr\\end{array}}} \n\\def\\|{\\!\\!\\smash{\\left|\\Height\\right.}\\!\\!} \n\\def\\Matrix#1{\\left[\\;\\;\\Height\\begin{array}{rrrcr}#1\\end{array}\\;\\;\\right]} $\n\nSystems of linear equations arise in all sorts of applications in many\ndifferent fields of study.  The method reviewed here can be\nimplemented to solve a linear system\n\n<\/p>\n\n\n\n<center>\n\t$\\begin{array}{ccccccccc}\n\t\ta_{11}x_{1} &amp; + &amp; a_{12}x_{2} &amp; + &amp; \\ldots &amp; + &amp; a_{1n}x_{n} &amp; = &amp; b_{1} \\\\\n\t\ta_{21}x_{1} &amp; + &amp; a_{22}x_{2} &amp; + &amp; \\ldots &amp; + &amp; a_{2n}x_{n} &amp; = &amp; b_{2} \\\\\n\t\t\\vdots &amp; &amp; \\vdots &amp; &amp; \\ddots &amp; &amp; \\vdots &amp; &amp; \\vdots \\\\\n\t\ta_{m1}z_{1} &amp; + &amp; a_{m2}x_{2} &amp; + &amp; \\ldots &amp; + &amp; a_{mn}x_{n} &amp; = &amp; b_{m} \\\\\n\t\\end{array}$\n<\/center>\n\n\n\n<p>\nof any size.  We write this system in matrix form as\n<\/p>\n\n\n\n<p>\n\t\t$$\n\t\t\\left[\\begin{array}{cccc}\n\t\t\ta_{11} &amp; a_{12} &amp; \\cdots &amp; a_{1n}\\\\\n\t\t\ta_{21} &amp; a_{22} &amp; \\cdots &amp; a_{2n}\\\\\n\t\t\t\\vdots &amp; \\vdots &amp; \\ddots &amp; \\ddots\\\\\n\t\t\ta_{m1} &amp; a_{m2} &amp; \\cdots &amp; a_{mn}\n\t\t\\end{array}\n\t\t\\right]\n\t\t\\left[\n\t\t\\begin{array}{c}\n\t\t\tx_1\\\\\n\t\t\tx_2\\\\\n\t\t\t\\vdots\\\\\n\t\t\tx_n\n\t\t\\end{array}\n\t\t\\right] =\n\t\t\\left[\n\t\t\\begin{array}{c}\n\t\t\tb_1\\\\\n\t\t\tb_2\\\\\n\t\t\t\\vdots\\\\\n\t\t\tb_m\n\t\t\\end{array}\n\t\t\\right]\n\t\t$$\n<\/p>\n\n\n\n<p>\n\t\t\tThat is, $ A{\\bf x} = {\\bf b}. $\n<\/p>\n\n\n\n<p>\nWe can capture all the information contained in the sytem in the\nsingle <b>augmented matrix<\/b>\n$$\n\\Matrix{\n\ta_{11} &amp; a_{12} &amp; \\cdots &amp; a_{1n} &amp;  &amp; b_{1}\\\\\n\ta_{21} &amp; a_{22} &amp; \\cdots &amp; a_{2n} &amp;\\|&amp; b_{2}\\\\\n\t\\vdots &amp; \\vdots &amp; \\ddots &amp; \\vdots &amp;\\|&amp; \\vdots\\\\\n\ta_{m1} &amp; a_{m2} &amp; \\cdots &amp; a_{mn} &amp;  &amp; b_{m}\\\\\n}\n$$\n\nWe will solve the original system of linear equations by performing a\nsequence of the following elementary row operations on the augmented\nmatrix: \n\n<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Elementary Row Operations<\/h4>\n\n\n\n<ul class=\"wp-block-list\"><li> Interchange two rows.\n\t\t\n\t\t\t<br><br>\n\t\t\t<\/li><li> Multiply one row by a nonzero number.\n\n\t\t\t<br><br>\n\t\t\t<\/li><li> Add a multiple of one row to a different row.\n\n\t\t<\/li><\/ul>\n\n\n\n<p>\n\t\t\tDo you see how we are manipulating the system of\n\t\t\tlinear equations by applying each of these operations?\n<\/p>\n\n\n\n<p>\nWhen a sequence of elementary row operations is performed on an\naugmented matrix, the linear system that corresponds to the resulting\naugmented matrix is equivalent to the original system.  That is, the\nresulting system has the same solution set as the original system.\nOur strategy in solving linear systems, therefore, is to take an\naugmented matrix for a system and carry it by means of elementary row\noperations to an equivalent augmented matrix from which the solutions\nof the system are easily obtained.  In particular, we bring the\naugmented matrix to Row-Echelon Form:\n\n<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Row-Echelon Form<\/h4>\n\n\n\n<p>\n\nA matrix is said to be in <b>row-echelon<\/b> form if \n\n<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li> All rows consisting entirely of zeros are at the bottom.\n\n\t<br><br>\n\t<\/li><li> In each row, the first non-zero entry form the left is a 1,\n\tcalled the <b>leading 1<\/b>.\n\n\t<br><br>\n\t<\/li><li> The leading 1 in each row is to the right of all leading 1&#8217;s in\n\t\tthe rows above it.\n\n<\/li><\/ol>\n\n\n\n<p>\nIf, in addition, each leading 1 is the only non-zero entry in its\ncolumn, then the matrix is in <b>reduced row-echelon form<\/b>.\n\n<\/p>\n\n\n\n<p> It can be proven that every matrix can be brought to row-echelon form, and even to reduced row-echelon form, by the use of elementary row operations.  At that point, the solutions of the system are easily obtained. <\/p>\n\n\n\n<p>\nIn the following example, suppose that each of the matrices was the\nresult of carrying an augmented matrix to reduced row-echelon form by\nmeans of a sequence of row operations.\n\n<\/p>\n\n\n\n<h6 class=\"wp-block-heading\">Example<\/h6>\n\n\n\n<p>\n\nThe augmented matrix\n$$\nA_{1} = \\Matrix{\n\t1 &amp; 0 &amp; 0 &amp;  &amp; 2\\\\\n\t0 &amp; 1 &amp; 0 &amp;\\|&amp; 3\\\\\n\t0 &amp; 0 &amp; 1 &amp;  &amp; -4 }\t\n$$\nin reduced row-echelon form, corresponds to the system\n\n<\/p>\n\n\n\n<center>\n\t$\\begin{array}{ccccr}\n\t\tx_1 &amp; &amp; &amp; = &amp; 2\\\\\n\t\t&amp; x_2 &amp; &amp; = &amp; 3\\\\\n\t\t&amp; &amp; x_3 &amp; = &amp;-4\n\t\\end{array}$\n<\/center>\n\n\n\n<p>\nwhich is already fully solved!\n\n<\/p>\n\n\n\n<p>\nThe augmented matrix\n$$\nA_{2} = \\Matrix{\n\t1 &amp; 0 &amp; -3 &amp; &amp; -5\\\\\n\t0 &amp; 1 &amp; 2 &amp;\\|&amp; 4\\\\\n\t0 &amp; 0 &amp; 0 &amp;  &amp; 0 }\n$$\nalso in reduced row-echelon form, corresponds to the system\n\n<\/p>\n\n\n\n<center>\n\t$\\begin{array}{ccrcr}\n\t\tx_1 &amp; &amp; -3x_3 &amp; = &amp; -5\\\\\n\t\t&amp; x_2 &amp; +2x_3 &amp; = &amp; 4\\\\\n\t\t&amp; &amp; 0 &amp; = &amp; 0\n\t\\end{array}$\n<\/center>\n\n\n\n<p>\nLetting $x_3=t$, we find that $x_2 = -2t+4$ and $x_1=3t-5$.  Thus, the\nsystem has infinitely many solutions, parametrized for all $t$ as\n$$\n\\left[\\begin{array}{c}\n\tx_1\\\\\n\tx_2\\\\\n\tx_3\n\\end{array}\\right] = \\left[\\begin{array}{c}\n\t3t-5\\\\\n\t-2t+4\\\\\n\tt\n\\end{array}\\right]\n$$\n\n<\/p>\n\n\n\n<p>\nFinally, the augmented matrix\n$$\nA_{3} = \\Matrix{\n\t1 &amp; 0 &amp; 0 &amp;  &amp; 3\\\\\n\t0 &amp; 1 &amp; 0 &amp;\\|&amp; 2\\\\\n\t0 &amp; 0 &amp; 0 &amp;  &amp; 1 }\n$$\nagain in reduced row-echelon form, corresponds to the system\n\n<\/p>\n\n\n\n<center>\n\t$\\begin{array}{ccccr}\n\t\tx_1 &amp; &amp; &amp; = &amp; 3\\\\\n\t\t&amp; x_2 &amp; &amp; = &amp; 2\\\\\n\t\t&amp; &amp; 0 &amp; = &amp; 1\n\t\\end{array}$\n<\/center>\n\n\n\n<p>\nwhich clearly has no solution.  The system is inconsistent.\n\n<\/p>\n\n\n\n<center>\n<h4>Notes<\/h4>\n<\/center>\n\n\n\n<ul class=\"wp-block-list\"><li> If a matrix is carried to row-echelon form by means of elementary row operations, the number of leading 1&#8217;s in the resulting matrix is called the <b>rank<\/b> $r$ of the original matrix. <br><br> <\/li><li> Suppose that a system of linear equations in $n$ variables has a solution.  Then the set of solutions has $n-r$ parameters, where $r$ is the rank of the augmented matrix. <br><br> <\/li><li> Suppose that $A$ is an $n \\times n$ <b>invertible<\/b> (has an inverse) matrix, which means it has an inverse. Then the system $A{\\bf x}= {\\bf b}$ has a unique solution given by ${\\bf x} = A^{-1}{\\bf b}$.  That is, the reduced row-echelon augmented matrix will be of the form $$ \\left[ I \\left| A^{-1}{\\bf b}\\right.\\right]. $$ <\/li><\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Gaussian Elimination<\/h4>\n\n\n\n<ol class=\"wp-block-list\"><li> If the matrix is already in row-echelon form, then stop.\n\n\t<br><br>\n\t<\/li><li> Otherwise, find the first column from the left with a non-zero\n\t\tentry $a$ and move the row containing that entry to the top of the\n\t\trows being worked on.\n\n\t<br><br>\n\t<\/li><li> Multiply that row by $1\/a$ to create a leading 1.\n\n\t<br><br>\n\t<\/li><li> Subtract multiples of that row from the rows below it to make\n\t\teach entry below the leading 1 zero.  We are now done working on that\n\t\trow.\n\n\t<br><br>\n\t<\/li><li> Repeat steps 1$-$4 on the rows still being worked on.\n\n<\/li><\/ol>\n\n\n\n<center>\n<h4>Notes<\/h4>\n<\/center>\n\n\n\n<ul class=\"wp-block-list\"><li> In practice, you have some flexibility in the application of the algorithm.  For instance, in Step 2 you often have a choice of rows to move to the top. <br><br> <\/li><li> A more computationally-intensive algorithm that takes a matrix to <b>reduced<\/b> row-echelon form is given by the Gauss-Jordon Reduction. <\/li><\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Example<\/h4>\n\n\n\n<p>\n\nWe will use Gaussian Elimination to solve the linear system\n\n<\/p>\n\n\n\n<center>$\\begin{array}{rcrcrcr}\n\t\tx_1 &amp; + &amp; 2x_2 &amp; + &amp; 3x_3 &amp; = &amp; 9 \\\\\n\t\t2x_1 &amp; &#8211; &amp; x_2 &amp; + &amp; x_3 &amp; = &amp; 8 \\\\\n\t\t3x_1 &amp; &amp; &amp; &#8211; &amp; x_3 &amp; = &amp; 3\n\t\\end{array}$.\n<\/center>\n\n\n\n<p>\nThe augmented matrix is\n$$\n\\Matrix{\n\t1 &amp; 2 &amp; 3 &amp;   &amp; 9\\\\\n\t2 &amp; -1 &amp; 1 &amp;\\|&amp; 8\\\\\n\t3 &amp; 0 &amp; -1 &amp;  &amp; 3 }\n$$\n\n<\/p>\n\n\n\n<p>\nThe Gaussian Elimination algorithm proceeds as follows:\n\n<\/p>\n\n\n\n<center>\n<table border=\"0\" align=\"center\">\n\t<tbody><tr>\n\t\t<td>\t$\\Matrix{\n\t\t\t\t1 &amp; 2 &amp; 3 &amp;   &amp; 9\\\\\n\t\t\t\t2 &amp; -1 &amp; 1 &amp;\\|&amp; 8\\\\\n\t\t\t\t3 &amp; 0 &amp; -1 &amp;  &amp; 3 }\n\t\t\t$\n\n\t\t<\/td><td>\t<table border=\"0\" align=\"center\">\n\t\t\t\t<tbody><tr><td> (Row 1) <\/td><\/tr>\n\t\t\t\t<tr><td> (Row 2) <\/td><\/tr>\n\t\t\t\t<tr><td> (Row 3) <\/td><\/tr>\n\t\t\t<\/tbody><\/table>\n\n\t\t<\/td><td> $$ \\quad\\longrightarrow\\quad $$\n\n\t\t<\/td><td>\t$\\Matrix{\n\t\t\t\t1 &amp; 2 &amp; 3 &amp;    &amp; 9\\\\\n\t\t\t\t0 &amp; -5 &amp; -5 &amp;\\|&amp; -10\\\\\n\t\t\t\t0 &amp; -6 &amp; -10 &amp; &amp; -24 }\n\t\t\t$\n\n\t\t<\/td><td>\t<table border=\"0\" align=\"left\">\n\t\t\t\t<tbody><tr><td> (Row 1) <\/td><\/tr>\n\t\t\t\t<tr><td> (Row 2$-2\\cdot$Row 1) <\/td><\/tr>\n\t\t\t\t<tr><td> (Row 3$-3\\cdot$Row 1) <\/td><\/tr>\n\t\t\t<\/tbody><\/table>\n\n\t<\/td><\/tr><tr>\n\t\t<td>\t<!--empty-->\n\n\t\t<\/td><td>\t<!--empty-->\n\n\t\t<\/td><td> $$ \\quad\\longrightarrow\\quad $$\n\n\t\t<\/td><td>\t$\\Matrix{\n\t\t\t\t1 &amp; 2 &amp; 3 &amp;   &amp; 9\\\\\n\t\t\t\t0 &amp; 1 &amp; 1 &amp;\\| &amp; 2\\\\\n\t\t\t\t0 &amp; -6 &amp; -10 &amp;&amp; -24 }\n\t\t\t$\n\n\t\t<\/td><td>\t<table border=\"0\" align=\"left\">\n\t\t\t\t<tbody><tr><td> (Row 1) <\/td><\/tr>\n\t\t\t\t<tr><td> ($-1\/5\\cdot$Row 2) <\/td><\/tr>\n\t\t\t\t<tr><td> (Row 3) <\/td><\/tr>\n\t\t\t<\/tbody><\/table>\n\n\t<\/td><\/tr><tr>\n\t\t<td>\t<!--empty-->\n\n\t\t<\/td><td>\t<!--empty-->\n\n\t\t<\/td><td> $$ \\quad\\longrightarrow\\quad $$\n\n\t\t<\/td><td>\t$\\Matrix{\n\t\t\t\t1 &amp; 2 &amp; 3 &amp;  &amp; 9\\\\\n\t\t\t\t0 &amp; 1 &amp; 1 &amp;\\|&amp; 2\\\\\n\t\t\t\t0 &amp; 0 &amp; -4 &amp; &amp; -12 }\n\t\t\t$\n\n\t\t<\/td><td>\t<table border=\"0\" align=\"left\">\n\t\t\t\t<tbody><tr><td> (Row 1) <\/td><\/tr>\n\t\t\t\t<tr><td> (Row 2) <\/td><\/tr>\n\t\t\t\t<tr><td> (Row 3$+6\\cdot$Row 2) <\/td><\/tr>\n\t\t\t<\/tbody><\/table>\n\n\t<\/td><\/tr><tr>\n\t\t<td>\t<!--empty-->\n\n\t\t<\/td><td>\t<!--empty-->\n\n\t\t<\/td><td> $$ \\quad\\longrightarrow\\quad $$\n\n\t\t<\/td><td>\t$\\Matrix{\n\t\t\t\t1 &amp; 2 &amp; 3 &amp;  &amp; 9\\\\\n\t\t\t\t0 &amp; 1 &amp; 1 &amp;\\|&amp; 2\\\\\n\t\t\t\t0 &amp; 0 &amp; 1 &amp;  &amp; 3 }\n\t\t\t$\n\n\t\t<\/td><td>\t<table border=\"0\" align=\"left\">\n\t\t\t\t<tbody><tr><td> (Row 1) <\/td><\/tr>\n\t\t\t\t<tr><td> (Row 2) <\/td><\/tr>\n\t\t\t\t<tr><td> ($-1\/4\\cdot$Row 3) <\/td><\/tr>\n\t\t\t<\/tbody><\/table>\n<\/td><\/tr><\/tbody><\/table>\n<\/center>\n\n\n\n<p>\nWe have brought the matrix to row-echelon form.  The corresponding\nsystem\n$$\\begin{array}{rrrrrcr}\n\tx_1 &amp; + &amp; 2x_2 &amp; + &amp; 3x_3 &amp; = &amp; 9\\\\\n\t    &amp;   &amp; x_2  &amp; + &amp; x_3  &amp; = &amp; 2\\\\\n\t    &amp;   &amp;      &amp;   &amp; x_3  &amp; = &amp; 3\n\\end{array}$$\n\n<\/p>\n\n\n\n<p>\nis easily solved from the bottom up:\n\\begin{eqnarray*}\n\t &amp; &amp; x_3 = 3 \\\\\n\t &amp; &amp; x_2+3=2 \\longrightarrow x_2 =-1\\\\\n\t &amp; &amp; x_1 +2(-1)+3(3)=9 \\longrightarrow x_1 =2.\\\\\n\\end{eqnarray*}\n\n<\/p>\n\n\n\n<p>\nThus, the solution of the original system is $x_1=2, \\quad x_2=-1,\n\\quad x_3=3.$\n\n<\/p>\n\n\n\n<p>\nIn the Exploration, use the Row Reduction Calculator to practice\nsolving systems of linear equations by reducing the augmented matrices\nto row-echelon form.\n\n<\/p>\n\n\n\n<p>Exploration<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<center>\n<h4>Key Concepts<\/h4>\n<\/center>\n\n\n\n<p> To solve a system of linear equations, reduce the corresponding augmented matrix to row-echelon form using the <strong>Elementary Row Operations<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li> Interchange two rows.\n\n\t<br><br>\n\t<\/li><li> Multiply one row by a nonzero number.\n\n\t<br><br>\n\t<\/li><li> Add a multiple of one row to a different row.\n\n<\/li><\/ul>\n\n\n\n<p>\nGaussian Elimination is one algorithm that reduces matrices to\nrow-echelon form.\n\n<!------------------------>\n\n\n<br>\n\n<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<p>\n\n[<a href=\"https:\/\/physics.hmc.edu\/ct\/quiz\/QZ3310\/\">I&#8217;m ready to take the quiz.<\/a>]\n[<a href=\"#top\">I need to review more.<\/a>]<br>\n\n\n<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Solving Systems of Linear Equations; Row Reduction &#8211; HMC Calculus Tutorial $\\def\\Height{\\vphantom{\\begin{array}{c}a\\cr a\\cr a\\cr\\end{array}}} \\def\\|{\\!\\!\\smash{\\left|\\Height\\right.}\\!\\!} \\def\\Matrix#1{\\left[\\;\\;\\Height\\begin{array}{rrrcr}#1\\end{array}\\;\\;\\right]} $ Systems of linear equations arise in all sorts of applications in many different fields of study. The method reviewed here can be implemented to solve a linear system $\\begin{array}{ccccccccc} a_{11}x_{1} &amp; + &amp; a_{12}x_{2} &amp; + &amp; \\ldots&hellip;<\/p>\n","protected":false},"author":5,"featured_media":0,"parent":61,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[],"class_list":["post-231","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/pages\/231","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/comments?post=231"}],"version-history":[{"count":8,"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/pages\/231\/revisions"}],"predecessor-version":[{"id":1237,"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/pages\/231\/revisions\/1237"}],"up":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/pages\/61"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/media?parent=231"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/calculus\/wp-json\/wp\/v2\/tags?post=231"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}