Linear system/Elimination method/Introduction/Section

Systems of linear equations are best solved by the elimination method, where successively a variable gets eliminated, and in the end we get an equivalent simple system which can be solved directly (or read of that there is no solution). For small systems, also the substitution method or the equating method are useful.

Definition

Let ${}K$ denote a field, and let two (inhomogeneous) systems of linear equations,

with respect to the same set of variables, be given. The systems are called equivalent, if their solution sets are identical.

Lemma

Let ${}K$ be a field, and let

${\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}&=&c_{1}\\a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}&=&c_{2}\\\vdots &\vdots &\vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}&=&c_{m}\end{matrix}}$

be an inhomogeneous system of linear equations over ${}K$. Then the following manipulations on this system yield an equivalent system.

1. Exchanging two equations.
2. The multiplication of an equation by a scalar ${}s\neq 0$.
3. The omitting of an equation, if it occurs twice.
4. The duplication of an equation (in the sense to write down the equation again).
5. The omitting or adding of a zero row (zero equation).
6. The replacement of an equation ${}H$ by the equation which arises if we add to ${}H$ another equation ${}G$ of the system.

Proof

Most of the statements are immediately clear. (2) follows from the fact that if

Failed to parse (syntax error): {\displaystyle {{}} \sum_{i <table class="metadata plainlinks ambox ambox-notice" style=""> <tr> <td class="mbox-image"><div style="width: 52px;"> [[File:Wikiversity logo 2017.svg|50px|link=]]</div></td> <td class="mbox-text" style=""> '''[[m:Soft redirect|Soft redirect]]'''<br />This page can be found at <span id="SoftRedirect">[[mw:Help:Magic words#Other]]</span>. </td> </tr> </table>[[Category:Wikiversity soft redirects|Linear system/Elimination method/Introduction/Section]] __NOINDEX__ 1}^n a_i \xi_i = c \, }

holds, then also

Failed to parse (syntax error): {\displaystyle {{}} \sum_{i <table class="metadata plainlinks ambox ambox-notice" style=""> <tr> <td class="mbox-image"><div style="width: 52px;"> [[File:Wikiversity logo 2017.svg|50px|link=]]</div></td> <td class="mbox-text" style=""> '''[[m:Soft redirect|Soft redirect]]'''<br />This page can be found at <span id="SoftRedirect">[[mw:Help:Magic words#Other]]</span>. </td> </tr> </table>[[Category:Wikiversity soft redirects|Linear system/Elimination method/Introduction/Section]] __NOINDEX__ 1}^n (s a_i) \xi_i = s c \, }

holds for every ${}s\in K$. If ${}s\neq 0$, then this implication can be reversed by multiplication with ${}s^{-1}$.

(6). Let ${}G$ be the equation

Failed to parse (syntax error): {\displaystyle {{}} \sum_{i <table class="metadata plainlinks ambox ambox-notice" style=""> <tr> <td class="mbox-image"><div style="width: 52px;"> [[File:Wikiversity logo 2017.svg|50px|link=]]</div></td> <td class="mbox-text" style=""> '''[[m:Soft redirect|Soft redirect]]'''<br />This page can be found at <span id="SoftRedirect">[[mw:Help:Magic words#Other]]</span>. </td> </tr> </table>[[Category:Wikiversity soft redirects|Linear system/Elimination method/Introduction/Section]] __NOINDEX__ 1}^n a_ix_i = c \, , }

and ${}H$ be the equation

Failed to parse (syntax error): {\displaystyle {{}} \sum_{i <table class="metadata plainlinks ambox ambox-notice" style=""> <tr> <td class="mbox-image"><div style="width: 52px;"> [[File:Wikiversity logo 2017.svg|50px|link=]]</div></td> <td class="mbox-text" style=""> '''[[m:Soft redirect|Soft redirect]]'''<br />This page can be found at <span id="SoftRedirect">[[mw:Help:Magic words#Other]]</span>. </td> </tr> </table>[[Category:Wikiversity soft redirects|Linear system/Elimination method/Introduction/Section]] __NOINDEX__ 1}^n b_ix_i = d \, . }

If a tuple ${}(\xi _{1},\ldots ,\xi _{n})\in K^{n}$ satisfies both equations, then it also satisfies the equation ${}H'=G+H$. And if the tuple satisfies the equations ${}G$ and ${}H'$, then it also satisfies the equation ${}G$ and ${}H=H'-G$.

$\Box$

For finding the solution of a linear system, the manipulations (2) and (6) are most important, where in general these two steps are combined, and the equation ${}H$ is replaced by an equation of the form ${}H+\lambda G$ (with ${}G\neq H$). Here, ${}\lambda \in K$ has to be chosen is such a way that the new equation contains one variable less than the old equation. This process is called elimination of a Variable. This elimination is not only applied to one equation, but for all equations except one (suitable chosen) "working row“ ${}G$, and with a fixed "working variable“. The following elimination lemma describes this step.

Lemma

Let ${}K$ denote a field, and let ${}S$ denote an (inhomogeneous) system of linear equations ${}K$ in the variables ${}x_{1},\ldots ,x_{n}$. Suppose that ${}x$ is a variable which occurs in at least one equation ${}G$ with a coefficient ${}a\neq 0$. Then every equation ${}H$, different from ${}G$, can be replaced by an equation ${}H'$ in which ${}x$ does not occur any more, and such that the new system of equations ${}S'$, which consists of ${}G$ and the equations ${}H'$, is equivalent with the system ${}S$.

Proof

Changing the numbering, we may assume ${}x=x_{1}$. Let ${}G$ be the equation

${}ax_{1}+\sum _{i=2}^{n}a_{i}x_{i}=b\,$

(with ${}a\neq 0$), and ${}H$ be the equation

${}cx_{1}+\sum _{i=2}^{n}c_{i}x_{i}=d\,.$

Then the equation

${}H'=H-{\frac {c}{a}}G\,$

has the form

${}\sum _{i=2}^{n}{\left(c_{i}-{\frac {c}{a}}a_{i}\right)}x_{i}=d-{\frac {c}{a}}b\,,$

and ${}x_{1}$ does not occur in it. Because of ${}H=H'+{\frac {c}{a}}G$, the systems are equivalent.

$\Box$

Theorem

Every (inhomogeneous) system of linear equations over a field ${}K$ can be transformed, by the manipulations described in

to an equivalent linear system of the form

${\begin{matrix}b_{1s_{1}}x_{s_{1}}&+b_{1s_{1}+1}x_{s_{1}+1}&\ldots &\ldots &\ldots &\ldots &\ldots &+b_{1n}x_{n}&=&d_{1}\\0&\ldots &0&b_{2s_{2}}x_{s_{2}}&\ldots &\ldots &\ldots &+b_{2n}x_{n}&=&d_{2}\\\vdots &\ddots &\ddots &\vdots &\vdots &\vdots &\vdots &\vdots &=&\vdots \\0&\ldots &\ldots &\ldots &0&b_{m{s_{m}}}x_{s_{m}}&\ldots &+b_{mn}x_{n}&=&d_{m}\\(0&\ldots &\ldots &\ldots &\ldots &\ldots &\ldots &0&=&d_{m+1}),\end{matrix}}$

where in each row, the first coefficient ${}b_{1s_{1}},b_{2s_{2}},\ldots ,b_{ms_{m}}$ is different from ${}0$. Here, either ${}d_{m+1}=0$, and the last row can be omitted, or ${}d_{m+1}=0$, and then the system has no solution at all.

Proof

This follows directly from the elimination lemma by eliminating successively variables. Elimination is applied firstly to the first variable (in the given ordering), say ${}x_{s_{1}}$, which occurs at all in at least one equation with a coefficient ${}\neq 0$ (if it only occurs in one equation, that the elimination step is done). This elimination process is applied as long as the new subsystem (without the working equation used in the elimination step before) has at least one equation with a coefficient for one variable different from ${}0$. After this, we have in the end only equations without variables, and they are either only zero equations, or there is no solution.

$\Box$

Lemma

Let an inhomogeneous system of linear equations in triangular form

${\begin{matrix}a_{11}x_{1}&+a_{12}x_{2}&\ldots &+a_{1m}x_{m}&\ldots &+a_{1n}x_{n}&=&c_{1}\\0&a_{22}x_{2}&\ldots &\ldots &\ldots &+a_{2n}x_{n}&=&c_{2}\\\vdots &\ddots &\ddots &\vdots &\vdots &\vdots &=&\vdots \\0&\ldots &0&a_{mm}x_{m}&\ldots &+a_{mn}x_{n}&=&c_{m}\\\end{matrix}}$

with ${}m\leq n$ over a field ${}K$ be given, where the diagonal elements are all not ${}0$. Then the solutions ${}(x_{1},\ldots ,x_{m},x_{m+1},\ldots ,x_{n})$ are in bijection with the tuples ${}(x_{m+1},\ldots ,x_{n})\in K^{n-m}$. The ${}n-m$ entries ${}x_{m+1},\ldots ,x_{n}$ can be chosen arbitrarily, and they determine a unique solution, and every solution is of this form.

Proof

This is clear, as when the tuple ${}(x_{m+1},\ldots ,x_{n})$ is given, the rows are determined successively from bottom to top.

$\Box$

For ${}m=n$, there are no free variables, and the linear system has exactly one solution.

Example

We want to solve the inhomogeneous linear system

${\begin{matrix}2x&+5y&+2z&&-v&=&3\\3x&-4y&&+u&+2v&=&1\\4x&&-2z&+2u&&=&7\,\end{matrix}}$

over ${}\mathbb {R}$ (or over ${}\mathbb {Q}$). Firstly, we eliminate ${}x$ by keeping the first row ${}I$, replacing the second row ${}II$ by ${}II-{\frac {3}{2}}I$, and replacing the third row ${}III$ by ${}III-2I$. This yields

${\begin{matrix}2x&+5y&+2z&&-v&=&3\\&-{\frac {23}{2}}y&-3z&+u&+{\frac {7}{2}}v&=&{\frac {-7}{2}}\\&-10y&-6z&+2u&+2v&=&1\,.\end{matrix}}$

Now, we can eliminate ${}y$ from the (new) third row, with the help of the second row. Because of the fractions, we rather eliminate ${}z$ (which eliminates also ${}u$). We leave the first and the second row as they are, and we replace the third row ${}III$ by ${}III-2II$. This yields the system, in a new ordering of the variables,

${\begin{matrix}2x&+2z&&+5y&-v&=&3\\&-3z&+u&-{\frac {23}{2}}y&+{\frac {7}{2}}v&=&{\frac {-7}{2}}\\&&&13y&-5v&=&8\,.\end{matrix}}$

Now we can choose an arbitrary (free) value for ${}v$. The third row determines then ${}y$ uniquely, we must have

${}y={\frac {8}{13}}+{\frac {5}{13}}v\,.$

In the second equation, we can choose ${}u$ arbitrarily, this determines ${}z$ via

${}{\begin{aligned}z&=-{\frac {1}{3}}{\left(-{\frac {7}{2}}-u-{\frac {7}{2}}v+{\frac {23}{2}}{\left({\frac {8}{13}}+{\frac {5}{13}}v\right)}\right)}\\&=-{\frac {1}{3}}{\left(-{\frac {7}{2}}-u-{\frac {7}{2}}v+{\frac {92}{13}}+{\frac {115}{26}}v\right)}\\&=-{\frac {1}{3}}{\left({\frac {93}{26}}-u+{\frac {12}{13}}v\right)}\\&=-{\frac {31}{26}}+{\frac {1}{3}}u-{\frac {4}{13}}v.\end{aligned}}$

The first row determines ${}x$, namely

${}{\begin{aligned}x&={\frac {1}{2}}{\left(3-2z-5y+v\right)}\\&={\frac {1}{2}}{\left(3-2{\left(-{\frac {31}{26}}+{\frac {1}{3}}u-{\frac {4}{13}}v\right)}-5{\left({\frac {8}{13}}+{\frac {5}{13}}v\right)}+v\right)}\\&={\frac {1}{2}}{\left({\frac {30}{13}}-{\frac {2}{3}}u-{\frac {4}{13}}v\right)}\\&={\frac {15}{13}}-{\frac {1}{3}}u-{\frac {2}{13}}v.\end{aligned}}$

Hence, the solution set is

${\left\{{\left({\frac {15}{13}}-{\frac {1}{3}}u-{\frac {2}{13}}v,{\frac {8}{13}}+{\frac {5}{13}}v,-{\frac {31}{26}}+{\frac {1}{3}}u-{\frac {4}{13}}v,u,v\right)}\mid u,v\in \mathbb {R} \right\}}.$

A particularly simple solution is obtained by equating the free variables ${}u$ and ${}v$ with ${}0$. This yields the special solution

${}(x,y,z,u,v)=\left({\frac {15}{13}},\,{\frac {8}{13}},\,-{\frac {31}{26}},\,0,\,0\right)\,.$

The general solution set can also be written as

${\left\{{\left({\frac {15}{13}},{\frac {8}{13}},-{\frac {31}{26}},0,0\right)}+u{\left(-{\frac {1}{3}},0,{\frac {1}{3}},1,0\right)}+v{\left(-{\frac {2}{13}},{\frac {5}{13}},-{\frac {4}{13}},0,1\right)}\mid u,v\in \mathbb {R} \right\}}.$

Here,

${\left\{u{\left(-{\frac {1}{3}},0,{\frac {1}{3}},1,0\right)}+v{\left(-{\frac {2}{13}},{\frac {5}{13}},-{\frac {4}{13}},0,1\right)}\mid u,v\in \mathbb {R} \right\}}$

is a description of the general solution of the corresponding homogeneous linear system.