Linear Systems
Table of Contents
1. Linear Systems
A linear system is a system of linear equations, which are equations with variables \(x_1, x_2, \ldots, x_n\) that can be written in the form \(a_1x_1 + \cdots + a_nx_n = b\). In traditional algebra, we can solve these systems using techniques such as substitution and elimination. However, for really large systems, these techniques become tedious and unwieldy.
Instead, we can use matrices to represent these equations in another way, for example:
\begin{aligned} \begin{bmatrix} a_1 & a_2 \\ b_1 & b_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} c_1 \\ c_2 \end{bmatrix} \end{aligned}The first matrix of constants is known as the coefficient matrix because it holds the coefficients of the linear system. We can append the constants to the matrix to form an augmented matrix, which holds all the information we need to describe the system:
\begin{aligned} \begin{bmatrix} a_1 & a_2 & c_1 \\ b_1 & b_2 & c_2 \end{bmatrix} \end{aligned}1.1. Elementary Row Operations
To solve the system, we can look to simplifying the augmented matrix. To do so, we can use row operations, which consist of:
- Replacement: replace a row by itself plus the multiple of another row
- Interchange: swap two different rows
- Scaling: multiply a row by a nonzero constant
These row operations can be seen as analogous to the operations we do on equations when we perform traditional algebra techniques such as elimination.
Two matrices are said to be row equivalent if one can be reached from the other using elementary row operations. If two systems have augmented matrices which are row equivalent, then they are the same system: they have the same solutions.
2. Linear Combinations
Given certain vectors, we can take linear combinations of those vectors. More generally, if we have vectors \(v_1, v_2, \dots, v_k\), we can take a linear combination of the vector with constants \(c\) by finding \(c_1v_1 + c_2v_2 + \cdots + c_kv_k\).
Multiplying a matrix \(A\) which is mxn and a vector which is nx1 can also be seen as a linear combination of the rows of \(A\):
\begin{aligned} \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} \\ \vdots \\ a_{m1} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \end{bmatrix} \end{aligned}2.1. Span
A natural question is to ask what vectors we can obtain by taking linear combinations of a certain set of vectors. For example, for two vectors \(v_1\) and \(v_2\) in \(\mathbb{R}^2\), do linear combinations of those two vectors create all of \(\mathbb{R}^2\)? We call the space created by all these linear combinations the span of the vector set.
Realize that this is equivalent to asking if each \(Ax=b\), where \(A\) is the matrix of the set of vectors, and \(b\) is any vector in \(\mathbb{R}^n\), is consistent. Therefore, the following 4 statements are equivalent:
- For all \(b\) in \(\mathbb{R}^m\), the equation \(Ax=b\) has a solution.
- Each \(b\) is a linear combination of the columns of \(A\).
- The columns of \(A\) span \(\mathbb{R}^m\).
- \(A\) has a pivot position in every row.
3. Solving Homogeneous Systems
A homogeneous matrix equation is one that can be represented with an mxn coefficient matrix \(A\) of \(n\) vectors in \(\mathbb{R}^m\), and an nx1 vector \(x\), like so:
\[ Ax = 0 \]
For a homogenous system like this, there is always the trivial solution \(x=0\). The question is, are there also some nonzero solutions \(x\) that work, i.e. a nontrivial solution? We can do this by putting \(A\) in row echelon form (note: the coefficient matrix, not the augmented one, since the augmented column will be 0 no matter what row operations we do) and solving the linear system. The system has a nontrivial solution if and only if there is at least one free variable.
3.1. Parametric Vector Form
We can also write our answers in parametric vector form. For example:
\begin{aligned} \begin{bmatrix}3x_2 - 2x_3 \\ x_2 \\ x_3\end{bmatrix} = x_2\begin{bmatrix}3 \\ 1\\ 0\end{bmatrix} + x_3\begin{bmatrix}-2 \\ 0 \\ 1 \end{bmatrix} \end{aligned}4. Solving Nonhomogeneous Systems
More generally, a nonhomogeneous matrix equation is one that can be represented by:
\[ Ax = b \]
To solve this system, there are two methods:
- Create augmented matrix and solve by reducing to row echelon form and back substitution.
- Find one solution to \(Ax=b\), and add that to the general solution to \(Ax=0\).
The second method works because if we set \(y\) to be that one solution (i.e. \(Ay=b\)), and then for any other solution \(z\) to the system, \(Az=b\), we have:
\[ A(y-z) = Ay- Az = b-b = 0 \]
Notice that here, \(y-z\) is the general solution to \(Ax=0\), and thus the general solution of \(Ax=b\) is just \((y-z) + z\).