Linear Equations

Systems of Linear Equations (SLE)

Recall that by 𝔽 we denote either the set of rational numbers, ℚ, or the set of real numbers, ℝ.

Definition 1. A system of m linear equations in n variables(or unknowns) over 𝔽 is a system of equations of the following form
(1) {[(a_11)*(x_1)+(a_12)*(x_2)+…+*(a_1*n)*(x_n)=(b_1)],[(a_21)*(x_1)+(a_22)*(x_2)+…+*(a_2*n)*(x_n)=(b_2)],[⋮],[(a_m1)*(x_1)+(a_m*2)*(x_2)+…+(a_mn)*(x_n)=(b_m)])
where (x_1), . . . , (x_n) are the variables, (a_ij)∈𝔽, i∈[m], j∈[n] are the given coefficients (of the system), and (b_i)∈𝔽, i=1,…m are the given constants (of the system). For example

{2*(x_1)-3*(x_2)=1), {[2*(x_1)+2*(x_2)=2],[(x_1)-(x_2)=0]), {[(x_1)+3*(x_2)+5*(x_3)=7],[3*(x_1)+5*(x_2)+7*(x_3)=9],[5*(x_1)+7*(x_2)+9*(x_3)=1]), {[2*(x_1)+(x_2)=0],[(x_1)-7*(x_2)=0],[-(x_1)-3*(x_2)=0],[(x_1)+(x_2)=0])

Let A=[[(a_11),(a_12),(a_13),…,(a_1*n)],[(a_21),(a_22),(a_23),…,(a_2*n)],[⋮,⋮,⋮,⋱,⋮],[(a_m1),(a_m*2),(a_m*3),…,(a_mn)]], x=[[(x_1)],[(x_2)],[⋮],[(x_n)]] and b=[[(b_1)],[(b_2)],[⋮],[(b_m)]] then system can be re-written as A*x=b (2)

In this setup, the matrix A is called the coefficient matrix of the linear system. For example, the systems in previous examples can be re-written as

(3) [[2,-3]]*[[(x_1)],[(x_2)]]=[1], [[2,2],[1,-1]]*[[(x_1)],[(x_2)]]=[[2],[0]], [[1,3,5],[3,5,7],[5,7,9]]*[[(x_1)],[(x_2)],[(x_3)]]=[[7],[9],[1]], [[2,1],[1,-7],[-1,-3],[1,1]]*[[(x_1)],[(x_2)]]=[[0],[0],[0],[0]]

Definition 2. System (1) is called homogeneous if (b_i)=0 for all i=1,…m(in matrix notation a homogeneous system is denoted by A*x=[0]). System (1) is called inhomogeneous (or non-homogeneous) if there is i such that (b_i)≠0. For example, the first three systems among examples are non-homogeneous, and the fourth one is homogeneous.

Definirion 3. A solution to the system A*x=b is a column vector с∈Mat(n),1, 𝔽)such that A*c indeed equals b

Definition 4. The solution setof the system A*x=b is the set of all solutions to A*x=b.

Definition 5. System A*x=b is called consistent if it admits a solution. System is called inconsistent if it admits no solution.

For example, any column vector [1/2 + 3λ/2, λ][1/2+(3*λ)/2,λ]⊺, where λ∈𝔽, is a solution to the first system in (3) (therefore, this system has at least as many solutions as there are elements in 𝔽); the column vector [1/2,1/2]⊺ is the unique solution to the second system in (3); the third system in (3) is inconsistent (it may not be obvious!); the column vector [0,0]⊺is the unique solution to the fourth system in (3). Note that any homogeneous system of linear equations is always consistent as a zero column vector (of an appropriate size) is its solution.

Lemma 1. If C∈Mat(m,m,𝔽) is an invertible matrix, then the linear systems A*x=b and C*A*x=C*b where A∈Mat(m,n,𝔽) and b∈Mat(m,1,𝔽), have the same solution set.
Proof. If u∈Mat(n,1,𝔽) is a solution to the left system, then it is clear thatuis a solution to theright one. Let u be a solution to the right system, and C(-1) be the inverse of C. Then we have A*u=(I_m)(A*u)=(C(-1)*C)*(A*u)=C(-1)*(C*A*u)=C(-1)*(C*b)=(C(-1)*C)*b=(I_m)*b=b∎

Theorem 1. Let R be the reduced row echelon form of matrix A∈Mat(m), n, 𝔽), b∈Mat(m,1,𝔽) and (E_1),(E_2),…,(E_k)∈Mat(m,m,𝔽) be elementary matrices such that (E_1)*(E_2)…(E_k)*A=R. Then the linear systems A*x=b and R*x=(E_1)*(E_2)…(E_k)*b, have the same solution set.

Let's try to solve some practical problems

Problem 1. Solve the system of linear equations R*x=b where R∈ Mat(m,n,𝔽) is reduced row echelon matrix, and b≠((b_j))∈ Mat(m,n,𝔽).
Solution. Let rows 1,…,r be all the non-zero rows of A, and suppose that the leading entry of row i occurs in column (k_i), for i∈[r]. If we let (y_1),…,(y_n-r) denote the (n-r) variables which are different from (x_(k_1)),…,(x_(k_r)), then our system is of the form
{[(x_(k_1))+(∑_j=1^n-r)((c_1*j)*(y_j))=(b_1)],[(x_(k_2))+(∑_j=1^n-r)((c_2*j)*(y_j))=(b_2)],[⋮],[(x_(k_r))+(∑_j=1^n-r)((с_r*j)*(y_j))=(b_r)],[0=(b_r+1)],[0=(b_r+2)],[⋮],[0=(b_m)]) (4)

From the form of the last (m-r) equations in (4), it follows that the condition for the system to have a solution is (b_j)=0, for r+1≤j≤m (indeed, for example, the (r+ 1)-th equation in (4) is of the form 0*(x_1)+…+0*(x_(k_r))+0*(y_1)+…+0*(y_n-r)=(b_r+1); if (b_r+1)≠0, this equation clearly has no solution). If this condition is satisfied, it should be clear that all the solutions to the system (4) are obtained by assigning any values whatsoever to (y_1),…,(y_n-r) and then computing the corresponding values of (x_(k_1)),…,(x_(k_r)) from (4). ∎

In the following example, we show how Problem1can be solved for a concrete system.Let us solve the system [[1,1,0,-2,3],[0,0,1,1,-1],[0,0,0,0,0]]*[[(x_1)],[(x_2)],[(x_3)],[(x_4)],[(x_5)]]=[[1],[-2],[0]]
In this case, r=2 (we have two non-zero rows), (k_1)=1 and (k_2)=3.Therefore we have (y_1)=(x_2),(y_2)=(x_4),(y_3)=(x_5), whence system (4) is of the form
{[(x_1)+1*(y_1)+(-2)*(y_2)+3*(y_3)=1],[(x_3)+0*(y_1)+1*(y_2)+(-1)*(y_3)=-2],[0=0]) (5)
Since (b_3)=0, the solution set of the system (5) consists of all the column-vectors of the form
[[1-(λ_1)+2*(λ_2)-3*(λ_3)],[(λ_1)],[-2-(λ_2)+(λ_3)],[(λ_2)],[(λ_3)]],
where (λ_1),(λ_2) and (λ_3) are arbitrary scalars from 𝔽.

Definition 6. If we have a system of linear equations of the form A*x=b, then a variable whose column in rref(A) contains a leading entry is called a leading variable. A variable whose column in rref(A) does not contain a leading entry is called a free variable. For example, variables (x_(k_1)),…,(x_(k_r)) in (4) are leading, and variables (y_1),…,(y_n-r) are free. In the above example, (x_1),(x_3) are the leading variables, and (x_2),(x_4),(x_5) are the free variables.

Now we introduce an easy-to-use notation for working with systems of linear equations
Definition 7. The augmented matrix of a system of linear equations (2), denoted (A|b), is the m-by-(n+1) matrix whose (i,j)-th entry is defined as

[(A|b)]*(i,j)≝{[[A]*(i,j)*if*j=1,…,n],[[b]*(i,1)*if*j=n+1])

That is

(A|b)=[[(a_11),(a_12),…,(a_1*n),(b_1)],[(a_21),(a_22),…,(a_2*n),(b_2)],[⋮,⋮,⋱,⋮,⋮],[(a_m1),(a_m*2),…,(a_mn),(b_m)]]

Note that if we pre-multiplied (i.e., multiplied from the left) a system A*x=b by a matrix C, arriving at a system C*A*x=C*b, then the augmented matrix of the last system is (C*A|C*b). Now we have an efficient method for solving systems of linear equations. Suppose we have a system of the form (2).
Step 1. form the augmented matrix, (A|b), of the system A*x=b;
Step 2. Find the elementary row operations (e_1),…,(e_k) such that ((e_1)∘…∘(e_k))*(A)=rref(A); by Theorem 1, the system A*x=b is equivalent to the system (reff*(A)|((e_1)∘(e_2)∘…∘(e_k))*(b));
Step 3. solve the last system as in Problem 1.