Jump to content

Linear system/Solution method/Introduction/Section

From Wikiversity

It is not clear a priori what solving a (linear) system of equation is supposed to mean. Anyway, the goal is to find a quite good description of the solution set. If there is only one solution, then we want to find it. If there is no solution at all, we want to detect this in a reasonable way. In general, the solution set of a system of equations is large. In this case, solving a system means to identify "free“ variables, for which arbitrary values are allowed, and to describe explicitly how the other "dependent“ variables can be expressed in terms of the free variables. This is called an explicit description of the solution set.

Linear systems of equations can be solved systematically with the elimination process. With this method, variables are eliminated step by step, until a very simple equivalent linear system in triangular form arises, which can be solved directly (or from where we can deduce that there is no solution). We consider a typical example in many variables.


We want to solve the inhomogeneous linear system

2x+5y+2z−v=33x−4y+u+2v=14x−2z+2u=7

over ℝ (or over ℚ). Firstly, we eliminate x by keeping the first row I, replacing the second row II by II−32I, and replacing the third row III by III−2I. This yields

2x+5y+2z−v=3−232y−3z+u+72v=−72−10y−6z+2u+2v=1.

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,[1]

2x+2z+5y−v=3−3z+u−232y+72v=−7213y−5v=8.

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

y=813+513v.

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

z=−13(−72−u−72v+232(813+513v))=−13(−72−u−72v+9213+11526v)=−13(9326−u+1213v)=−3126+13u−413v.

The first row determines x, namely

x=12(3−2z−5y+v)=12(3−2(−3126+13u−413v)−5(813+513v)+v)=12(3013−23u−413v)=1513−13u−213v.

Hence, the solution set is

{(1513−13u−213v,813+513v,−3126+13u−413v,u,v)∣u,v∈ℝ}.

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)=(1513,813,−3126,0,0).

The general solution set can also be written as

{(1513,813,−3126,0,0)+u(−13,0,13,1,0)+v(−213,513,−413,0,1)∣u,v∈ℝ}.

Here,

{u(−13,0,13,1,0)+v(−213,513,−413,0,1)∣u,v∈ℝ}

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


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

a11x1+a12x2+⋯+a1nxn=c1a21x1+a22x2+⋯+a2nxn=c2⋮⋮⋮am1x1+am2x2+⋯+amnxn=cm

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

  1. Swapping two equations.
  2. The multiplication of an equation by a scalar s≠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 that arises if we add to H another equation G of the system.

Proof  

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

∑i=1naiξi=c

holds, then also

∑i=1n(sai)ξi=sc

holds for every s∈K. If s≠0, then this implication can be reversed by multiplication with s−1.

(6). Let G be the equation

∑i=1naixi=c,

and H be the equation

∑i=1nbixi=d.

If a tuple (ξ1,…,ξn)∈Kn 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.

◻


For finding the solution set of a linear system, the manipulations (2) and (6) are most important. In general, these two steps are combined, and the equation H is replaced by an equation of the form H+λG (with G≠H). Here, λ∈K has to be chosen in 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 over K in the variables x1,…,xn. Suppose that x is a variable which occurs in at least one equation G with a coefficient a≠0. Then every equation H, different from G,[2] can be replaced by an equation H′, in which x does not occur any more, and such that the new system of equations S′ that consists of G and the equations H′, is equivalent to the system S.

Proof  

Changing the numbering, we may assume x=x1. Let G be the equation

ax1+∑i=2naixi=b

(with a≠0), and let H be the equation

cx1+∑i=2ncixi=d.

Then the equation

H′=H−caG

has the form

∑i=2n(ci−caai)xi=d−cab,

and x1 does not occur in it. Because of H=H′+caG, the systems are equivalent.

◻


The method of this lemma, called Gauß elimination process, can be applied successively in order to obtain a linear system in triangular form.


Theorem

Every (inhomogeneous) system of linear equations over a field K can be transformed, by the manipulations described in fact, to an equivalent linear system of the form

b1s1xs1+b1s1+1xs1+1……………+b1nxn=d10…0b2s2xs2………+b2nxn=d2⋮⋱⋱⋮⋮⋮⋮⋮=⋮0………0bmsmxsm…+bmnxn=dm(0………………0=dm+1),

where, in each row, the first coefficient b1s1,b2s2,…,bmsm is different from 0. Here, either dm+1=0, and the last row can be omitted, or dm+1=0, and then the system has no solution at all.

With the help of renaming the variables, we get an equivalent system of the form

c11y1+c12y2…+c1mym+c1m+1ym+1…+c1nyn=d10c22y2…………+c2nyn=d2⋮⋱⋱⋮⋮⋮⋮=⋮0…0cmmym+cmm+1ym+1…+cmnyn=dm(0……00…0=dm+1)

with diagonal elements

cii≠0.

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 xs1, which occurs in at least one equation with a coefficient ≠0 (if it only occurs in one equation, then this elimination step is already 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.

When we set y1=xs1,y2=xs2,…,ym=xsm, and denote the other variables with ym+1,…,yn, then we obtain the described system in triangular form.

◻


It might happen that the variable x1 does not appear in the system with a coefficient ≠0, and that, in the elimination process, more than one variable is eliminated at the same time. Then one gets a linear system in echelon form, which can be transformed to a triangular form by a change of variables.

  1. ↑ Such a reordering is safe as long as we keep the names of the variables. But if we write down the system in matrix notation without the variables, then one has to be careful and remember the reordering of the columns.
  2. ↑ It is enough that these equations have a different index in the system.