An m × n matrix A is both a list of rows, acting as linear
functions on 𝔽^{m}, and a list of columns, representing vectors
in 𝔽^{m}. Accordingly, we can interpret matrix/vector multiplication in dual ways: As a transformation of the input vector,
or as a linear combination of the matrix columns.
Setting up
A linear equation with n unknowns is an expression of the form
where, for i = 1, 2, …, n, the 田_{i}’s are the unknowns, or variables, the 𝑎_{i}’s are scalars from field 𝔽 (which is either the set of real numbers ℝ or complex numbers ℂ), called coefficients of the unknowns and b is the constant term, or simply
the constant of the equation. Coefficients of the equation and constant term are given (or known), but unknown variables are subject to be determination and any character can be used for their notation. We prefer to use indexed variable rather than letters or characters because we will treat them as components of an unknwn vector.
A solution of the linear equation is an n-tuple (s_{1}, s_{2}, … , s_{n}) of scalars that upon substituting these numbers s_{i} for the variables 田_{i} gives a true statement:
The n-tuple (s_{1}, s_{2}, … , s_{n}) is said to satisfy the given linear equation, and the equation is said to be consistent
or compatible. If an n-tuple satisfying the given equation does not exist, then the equation is said
to be inconsistent or incompatible.
A linear system in standard form consists of m equations in n unknowns
x_{1}, x_{2}, ... , x_{n} is
expressed as
respectively. The unknown vector x = (x_{1}, x_{2}, … , x_{n}) can also be written in column form.
Then the above system could be written in a compact form A x = b.
A solution to the the linear system of equations is an n-tuple
< s_{1}, s_{2}, ... , s_{n}
> of complex or real numbers that satisfies the vector equation
A s = b. The set of all solutions to the system
A x = b is called the solution set or the general solution of the system.
A linear system A x = b is called homogeneous provided the
right side b = 0. Every homogeneous linear system can be
represented as a vector equation A x = 0.
A linear system Ax = b is called nonhomogeneous
(or inhomogeneous) provided that b ≠ 0. For a given
nonhomogeneous linear system of equations A x = b, the linear
system Ax = 0 is called associated homogeneous system.
Solving Systems of Linear Equations
Being able to solve systems of many linear equations in many unknowns is a vital part of linear algebra.
A homogeneous linear equation A x = 0 always has an obvious
solution x = 0; we call 0 the
trivial solution. We will learn in the next
chapter that some homogeneous linear systems
have solutions other than the trivial solution; such solutions are called
nontrivial.
Corollary:
If m < n, the system Ax = 0 has a nonzero
solution.
Example 1:
Consider the system of algebraic equations
be the coefficient matrix of this system. With Mathematica, it is
easy to find nontrivial solutions of the system Ax = 0:
NullSpace[{{1, 2, -1}, {2, 1, -2}}]
{{4, -1, 2}}
So any vector that is proportional to [ 4, -1, 2 ] is a solution to the given
homogeneous system of linear equations.
■
End of Example 1
If A is an m×n matrix, the general solution or solution set of the linear system A x = b is the sum of a particular solution of the
system A x = b and a linear combination
c_{1}v_{1} +
c_{2}v_{2} + ⋯ +
c_{k}v_{k} of solutions
v_{1}, v_{2}, ... , v_{k} of the
homogeneous system Av = 0.
The following theorem is the main statement about solvability of the nonhomogeneous system of equation. It will be proved later in part 3.
Theorem 1:
Let A be an m×n matrix and b be an m-vector. The
the linear matrix/vector equation A x = b has a solution if and only if
b is orthogonal to every solution y (so its dot product b
• y = 0 is zero)
of the homogeneous equation A^{*}y = 0, where
A^{*} is the n×m matrix obtained from A by
transposition and taking complex conjugate. Recall that A^{*} is
called the adjoint matrix to A.
Example 2:
We consider the following system of equations:
■
End of Example 2
Theorem 2: Let A be an
m×n matrix.
(Overdetermined Case) If m ≥ n, then the linear system
Ax = b is consistent for at least one vector b in
ℝ^{m}.
(Underdetermined Case) If m ≤ n, then for each vector
b in ℝ^{m} the linear system
Ax = b is either inconsistent or has infinitely many solutions.
Example 3:
■
End of Example 3
Suppose that a matrix A is transformed/equivalent to the row
echelon matrix B by elementary row operations. This means that every
nonzero row in matrix B has a leading entry, which is the leftmost
nonzero entry in a nonzero row and all entries below it are zeroes.
A pivot position in a matrix A is a location in A that
corresponds to a leading term in B, the echelon form of A. A
pivot column is a column of A that contains a pivot position.
Theorem 3: An m×n
linear system A x = b in variables x_{1},
x_{2}, ... , x_{n} is consistent (that is, it
has a solution) for all b∈ℝ^{m} if and only if the
reduced echelon form of A has m pivots.
For the linear system Ax = b, let the augmented matrix
[A|b] is transformed to the row echelon form B. If the
last column of B is a pivot column, then the system is inconsistent
since B contains a row of the form
\[
\left[ 0 \ 0 \ \cdots \ 0 \ * \right] ,
\]
where * is a nonzero number. This corresponds to the contradictory equation
0ċx_{n} = *. Hence the number of pivot columns of the
augmented matrix cannot exceed the number of pivot columns of A, if
the system is to be consistent. Moreover, the number of pivot columns of
A cannot exceed the number of rows of A because no two pivots
of a matrix can occur in the same row.
Suppose, therefore, that the reduced row echelon form (we use the reduced form
instead of the echelon form for simplicity because it does not matter) B
of the augmented matrix has m pivots. Then the m-th row of
B is of the form
In that case, we can assign values to the variables x_{j+1},
x_{j+2}, ... , x_{n}, solve for
x_{m}, and use back substitution to build a solution
b∈ℝ^{m} for the system. This clearly works for any
assignment of values to the variables x_{i}. On the other hand,
if the number of pivots of B is less than m, then B
contains a row of the form
If we let b = [ b_{1}, ... , b_{i}, ... ,
b_{m} ] be any vector in ℝ^{m}, in which
\( b_i = b_{i(n+1)} \ne 0, \) the system
Ax = b is inconsistent. Hence, there exists a vector
b∈ℝ^{m} that is not a solution of
Ax = b. This proves the theorem.
Example 4: Consider the linear system of equations
Since matrix A has only 3 pivots (marked bold font), the given system
has a solution not for arbitrary input vector b. One solution can be
identified to be p = [1,-1,2,3], but the general solution, according to
Mathematica
because the solution set of the associated homogeneous equation Ax =
0 is spanned on the vector [-10, 9, -2, 11] .
On the other hand, if try
to solve the same system of linear equations for another input vector
b = [1,-1,2,2], we will be in bad luck---there is no solution.
Indeed, Mathematica provides the reduced row echelon form: