An n × m 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.
respectively. The unknown vector x can also be written in column form.
Then the above system could be written in a compact form Ax = 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
As = b. The set of all solutions to the system
Ax = b is called the solution set of the system.
A linear system Ax = b is called homogeneous provided the
right side b = 0. Every homogeneous linear system can be
represented as a vector equation Ax = 0.
A linear system Ax = b is called nonhomogeneous
(or inhomogeneous) provided that b ≠ 0. For a given
nonhomogeneous linear system of equations Ax = b, the linear
system Ax = 0 is called associated homogeneous system.
A homogeneous linear equation Ax = 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: 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.
■
If A is an m×n matrix, the general solution of the
linear system Ax = b is the sum of a particular solution of the
system Ax = 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:
Let A be an m×n matrix and b be an m-vector. The
the linear vector equation Ax = 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.
Theorem: 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.
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: An m×n
linear system Ax = 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 sonsistent. 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 teh 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 otehr 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.
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: