Systems of linear equations

Contents

Definition
Representation as functions.
Theorems.
i) Systems only have 0, 1 or infinite solutions.
ii) Sth here
iii) If number of variables equals the number of equations.

Definition

A system of linear equations is a set of equations of the form,

$\begin{array}{cccccc} \alpha_1 x_1 &+&...&+&\alpha_n x_n & = m_1 \\ \beta_1 x_1 &+&...& +&\beta_n x_n & = m_2 \\ &\vdots & & \vdots \\ \lambda_1 x_1 &+&...& +&\lambda_n x_n & = m_n \end{array}$

If the system of equations has at least one solution, then we refer to the system of equations as being consistent, or inconsistent otherwise. If a system is consistent and has only one solution, we say that the system is definite. If the system has more than one solution, we say the system is indefinite.

Representation as Functions

We can represent the system of linear equations using functions. Let $f$ be a linear function which maps from all possible sets of inputs, $\mathbf{x} = (x_1, ..., x_n)$ , to the real numbers. Then, we have the system,

$\begin{array}{ccc} f_1(\mathbf{x}) &= &m_1 \\ f_2(\mathbf{x}) &= &m_2 \\ \vdots && \vdots \\ f_n(\mathbf{x}) &= &m_n \end{array}$

Theorems

Theorem 1 – A system of linear equations has either zero, one, or an infinite number of solutions.

Proof – We construct a system which has no solutions, for example consider

$\begin{array}{cccc} 2x &+ & 5y &=6 \\ 2x &+ & 5y &=7 \end{array}$

which would imply that the sum of $2x$ and $5y$ must equal both $6$ and $7$ , however by the field axioms, we have that the sum of two elements of $F$ is unique, which gives a contradiction.

We may also develop a system with just one solution, for example consider

$\begin{array}{cccc} 7x &+ & 5y &=6 \\ 2x &+ & 5y &=7 \end{array}$ .

Finally, imagine that we have two distinct solution vectors, $\mathbf{t}$ and $\mathbf{s}$ . Then, it follows that the new vector $k(\mathbf{t} -\mathbf{s}) + \mathbf{t}$ is also a solution to the system of equations, since for every equation $f_i(\mathbf{x}) = m_i$ , we have that

$f_i(k(\mathbf{t} -\mathbf{s}) + \mathbf{t}) \\\\ = f_i(k(\mathbf{s}-\mathbf{t})) + f_i(\mathbf{t}) \\\\ = kf_i(\mathbf{s}-\mathbf{t}) + f_i(\mathbf{t}) \\\\ = k[f_i(\mathbf{s})-f_i(\mathbf{t})] + f_i(\mathbf{t}) \\\\ = k[0] + f_i(\mathbf{t}) \\\\ = f_i(\mathbf{t}) \\\\ = m_i$

using the properties of a linear function, as well as $\mathbf{s}$ and $\mathbf{t}$ being solutions of the form $(x_1, ..., x_n)$ . Now, since by assumption we have that $\mathbf{s}$ and $\mathbf{t}$ are distinct, we have that for each $k$ , the solution $k(\mathbf{t} -\mathbf{s}) + \mathbf{t}$ is a new solution, and hence there are infinitely many such solutions.

Theorem 2 – A system of linear equations with $n$ variables and $k$ equations is inconsistent if there are less than $n$ equations.

Proof – We will prove this by induction. For the base case, consider $k=1$ equations, ie

$\alpha_1 x_1 + ... + \alpha_n x_n = m_1$ .

We can easily rearrange one of the variables such that it is a function of the remaining variables, which implies that we have an infinite number of possible solutions. Now we assume that the hypothesis is true for all $n \leq k$ . Then, it follows that either the system of $k$ equations has either no solutions or an infinite number of solutions. If it has no solutions, adding another equation to the system will not make the system consistent. If the $k$ equations have an infinite number of solutions, then it follows that at least one of the variables must have an infinite number of possible values.

If all the $k$ equations have an infinite number of solutions, we may eliminate (at least) one of the variables from all but one equation by subtracting, from each $f_i(\mathbf{x}) = m_i$ , the equation $k*f_{i+1}(\mathbf{x}) = m_{i+1}$ for some $k\in \mathbb{R}$ . This leaves us with a new system of equations such that $f_1(\mathbf{x}) = m_1$ , and

$\begin{array}{cccccccc} \alpha_1 x_1 &+& \alpha_2 x_2&+&...&+&\alpha_n x_n & = m_1 \\ &&\beta_2 x_2&+&...& +&\beta_n x_n & = m_2 \\ &&&\vdots & & \vdots \\ &&\lambda_2 x_2&+&...& +&\lambda_n x_n & = m_k \end{array}$

Now, we know that, by hypothesis, the set of equations

$\begin{array}{ccccccc} \alpha_2 x_2&+&...&+&\alpha_n x_n & = m_1 \\ \beta_2 x_2&+&...& +&\beta_n x_n & = m_2 \\ &\vdots & & \vdots \\ \lambda_2 x_2&+&...& +&\lambda_n x_n & = m_k \end{array}$

are inconsistent by hypothesis, but since they are inconsistent, adding another variable to the top equation will not make them consistent, as the solution to the system of equations depends only on the coefficients, and so the equations will be inconsistent for all $m_1 - \alpha_1 x_1$ . This completes the proof.

Theorem 3 – If the number of equations equal the number of unknowns, then the property of having a unique solution depends solely on the coefficients of the system.

Proof – The result may be obtained via induction on the number of equations (which equals the number of unknowns). Let $a,b,c,d \in \mathbb{R}\setminus \{0\}$

Let us consider the base case, $n=2$ . We have the set of equations,

$\begin{array}{cccc} ax &+ & by &=m_1 \\ cx &+ & dy &=m_2 \end{array} \iff \begin{array}{cccc} ax &+ & by &=m_1 \\ ax &+ & \frac{ad}{c}y &= \frac{ad}{c}m_2 \end{array}$

But this implies that $y = \frac{m_1 - \frac{ad}{c}m_2}{b-\frac{ad}{c}}$ . The existence of an $r = \frac{m_1 - \frac{ad}{c}m_2}{b-\frac{ad}{c}} \in \mathbb{R}$ depends on the condition that $b-\frac{ad}{c} \neq 0$ . But this means that the condition for the existence of a unique solution for one of the variables depends entirely on the coefficients of the system of linear equations. As our choice of which variable to solve for was arbitrary, the same applies to the other three variables. This proves the base case.

We now prove that if the hypothesis is true for some $n=k\in\mathbb{N}$ with $k> 2$ . By assumption, we have that the system of equations

$\begin{array}{cccccc} \alpha_1 x_1 &+&...&+&\alpha_k x_k & = m_1 \\ \beta_1 x_1 &+&...& +&\beta_k x_k & = m_2 \\ &\vdots & & \vdots \\ \lambda_1 x_1 &+&...& +&\lambda_k x_k & = m_k \end{array}$

Note that this representation does not exclude the possibility of $k=3$ . Now, as the solution does not depend on the values $m_1, ..., m_k$ , let $n_i = m_i + a_i$ , where each $a_i$ is any element $a_i \in \mathbb{R}$ .

If we add another variable, $x_{k+1}$ and another equation (so that the number of unknowns still equals the number of equations, where the number of equations is $k+1$ ), then we have the system

$\begin{array}{ccccccccc} \alpha_1 x_1 &+&...&+&\alpha_k x_k&+&\alpha_{k+1}x_{k+1} & =& m_1 + q_1 \\ \beta_1 x_1 &+&...&+&\beta_k x_k&+&\beta_{k+1}x_{k+1} & =& m_2 +q_2\\ &\vdots & & \vdots &&&\vdots\\ \lambda_1 x_1 &+&...&+&\lambda_k x_k&+&\lambda_{k+1}x_{k+1} & = &m_k +q_k\\ \sigma_1 x_1 &+&...&+&\sigma_k x_k&+&\sigma_{k+1}x_{k+1}& = &m_{k+1} +q_{k+1}\end{array}$

For all $q_i \in\mathbb{R}$ . But, by hypothesis, for any $(m_1,...,m_k)$ , there is a unique solution to the system of equations

$\begin{array}{cccccc} \alpha_1 x_1 &+&...&+&\alpha_k x_k & = m_1 \\ \beta_1 x_1 &+&...& +&\beta_k x_k & = m_2 \\ &\vdots & & \vdots \\ \lambda_1 x_1 &+&...& +&\lambda_k x_k & = m_k \end{array}$

Now, this means we can write the set of $k+1$ equations (substituting in their unique solution), as

$\begin{array}{cccc} \alpha_{k+1}x_{k+1} & =& q_1 \\ \beta_{k+1}x_{k+1} & =& q_2\\ &\vdots &\\ \lambda_{k+1}x_{k+1} & = &q_k\\ \sigma_{k+1}x_{k+1} & = &q_{k+1}\end{array}$

But this implies that

$x_{k+1} = \frac{q_1 + q_2 + ... + 1_k + q_{k+1}}{\alpha_{k+1} + \beta_{k+1} + ... + \lambda_{k+1} + \sigma_{k+1}}$

And so the only condition for $x_{k+1}$ is that $\alpha_{k+1}, \beta_{k+1}, ..., \lambda_{k+1}, \sigma_{k+1} \neq 0$ , and so the existence of a unique solution again depends only on the coefficients. This proves the theorem.

Theorem 4 – Consider a system of linear equations with $n$ equations and $n$ variables,

$\begin{array}{cccccc} \alpha_1 x_1 &+&...&+&\alpha_n x_n & = m_1 \\ \beta_1 x_1 &+&...& +&\beta_n x_n & = m_2 \\ &\vdots & & \vdots \\ \lambda_1 x_1 &+&...& +&\lambda_n x_n & = m_n \end{array}$

And now consider the homogenous set of equations

$\begin{array}{cccccc} \alpha_1 x_1 &+&...&+&\alpha_n x_n & = 0 \\ \beta_1 x_1 &+&...& +&\beta_n x_n & = 0 \\ &\vdots & & \vdots \\ \lambda_1 x_1 &+&...& +&\lambda_n x_n & = 0 \end{array}$

Where the coefficients remain unchanged. Then, the original system of equations has a unique set of solutions if and only if the homogenous system of equations has no other set of solutions other than the null solution.

Proof – In the first case, assume that the original system of equations has a unique solution. Then, from theorem 3, it follows that the homogeneous system has a unique solution. However, the solution $x_i = 0$ for all $i = 1,...,n$ is a solution to the system of equations, and so is the only solution.

Conversely, if the homogeneous system has only the null solution, then this is due to the coefficients (by theorem 3), and so we have that the same is true for any system (not only the homogeneous system), and thus the original system of equations only have one solution. $\square$