Solving Systems of Linear Equations

A system of linear equations is a collection of two or more linear equations involving the same set of variables. Solving such systems is a fundamental problem in linear algebra, with applications across various fields, including engineering, physics, computer science, and economics. This article explores the key methods for solving systems of linear equations.

---

1. What is a System of Linear Equations?

A system of linear equations consists of multiple linear equations that share a common set of variables. A solution to the system is a set of values for the variables that satisfy all the equations simultaneously.

1.1 Example of a System of Linear Equations

Consider the following system of two equations in two variables, $x$ and $y$:

$$\begin{aligned} 3x + 4y &= 10 \\ 2x - y &= 3 \end{aligned}$$

The goal is to find values for $x$ and $y$ that satisfy both equations.

---

2. Methods for Solving Systems of Linear Equations

There are several methods for solving systems of linear equations. These methods can be broadly classified into algebraic methods (like substitution and elimination) and matrix methods (like Gaussian elimination and LU decomposition).

2.1 Substitution Method

The substitution method involves solving one of the equations for one variable and then substituting this expression into the other equations.

Steps:

1. Solve one equation for one variable: Choose one of the equations and solve it for one of the variables in terms of the other.
2. Substitute into the other equation: Substitute the expression found in step 1 into the other equation to eliminate one variable.
3. Solve the resulting equation: This will give you the value of one variable.
4. Back-substitute to find the remaining variable: Substitute the value found in step 3 back into the expression from step 1 to find the other variable.

Example:

Given the system:

$$\begin{aligned} x + 2y &= 5 \\ 3x - y &= 4 \end{aligned}$$

Step 1: Solve the first equation for $x$:

$$x = 5 - 2y$$

Step 2: Substitute into the second equation:

$$3(5 - 2y) - y = 4 \\ 15 - 6y - y = 4 \\ -7y = -11 \\ y = \frac{11}{7}$$

Step 3: Substitute $y = \frac{11}{7}$ into $x = 5 - 2y$:

$$x = 5 - 2\left(\frac{11}{7}\right) = \frac{24}{7}$$

So, the solution is $x = \frac{24}{7}$, $y = \frac{11}{7}$.

2.2 Elimination Method

The elimination method involves adding or subtracting the equations to eliminate one of the variables, reducing the system to a simpler one.

Steps:

1. Multiply the equations if necessary: Multiply one or both of the equations by constants so that the coefficients of one variable are the same.
2. Add or subtract the equations: This will eliminate one variable, leaving an equation with a single variable.
3. Solve the resulting equation: Find the value of the remaining variable.
4. Substitute back to find the other variable: Use the value found to solve for the other variable in one of the original equations.

Example:

Given the system:

$$\begin{aligned} 2x + 3y &= 7 \\ 4x - 3y &= 1 \end{aligned}$$

Step 1: Add the two equations to eliminate $y$:

$$(2x + 3y) + (4x - 3y) = 7 + 1 \\ 6x = 8 \\ x = \frac{8}{6} = \frac{4}{3}$$

Step 2: Substitute $x = \frac{4}{3}$ into the first equation:

$$2\left(\frac{4}{3}\right) + 3y = 7 \\ \frac{8}{3} + 3y = 7 \\ 3y = 7 - \frac{8}{3} = \frac{21}{3} - \frac{8}{3} = \frac{13}{3} \\ y = \frac{13}{9}$$

So, the solution is $x = \frac{4}{3}$, $y = \frac{13}{9}$.

---

3. Gaussian Elimination

Gaussian elimination is a systematic method for solving systems of linear equations using matrix operations. The method transforms the system's augmented matrix into row-echelon form, from which the solutions can be easily obtained.

3.1 Row Operations

Gaussian elimination involves three types of row operations:

1. Row swapping: Swap two rows.
2. Row multiplication: Multiply a row by a non-zero scalar.
3. Row addition: Add a multiple of one row to another row.

3.2 Steps of Gaussian Elimination

1. Form the augmented matrix: Write the system of equations as an augmented matrix.
2. Apply row operations: Use row operations to convert the matrix into upper triangular form (row-echelon form).
3. Back substitution: Solve the system by back substitution, starting from the last row.

3.3 Example

For the system:

$$\begin{aligned} x + 2y + z &= 4 \\ 2x + 3y + 2z &= 9 \\ 3x + 2y + 3z &= 14 \end{aligned}$$

The augmented matrix is:

$$\begin{pmatrix} 1 & 2 & 1 & | & 4 \\ 2 & 3 & 2 & | & 9 \\ 3 & 2 & 3 & | & 14 \end{pmatrix}$$

Step 1: Subtract 2 times the first row from the second row and 3 times the first row from the third row:

$$\begin{pmatrix} 1 & 2 & 1 & | & 4 \\ 0 & -1 & 0 & | & 1 \\ 0 & -4 & 0 & | & 2 \end{pmatrix}$$

Step 2: Subtract 4 times the second row from the third row:

$$\begin{pmatrix} 1 & 2 & 1 & | & 4 \\ 0 & -1 & 0 & | & 1 \\ 0 & 0 & 0 & | & 0 \end{pmatrix}$$

Step 3: Back-substitution: Start from the last non-zero row and solve upwards:

• $y = -1$

• Substitute $y = -1$ into the first row to solve for $x$: $x + 2(-1) + z = 4 \rightarrow x + z = 6$

  Choose $z$ to satisfy $x + z = 6$, so for example, $x = 5$ and $z = 1$.

So, the solution can be expressed as $(x, y, z) = (5, -1, 1)$.

---

4. LU Decomposition

LU decomposition is a matrix factorization method where a matrix is decomposed into the product of a lower triangular matrix (L) and an upper triangular matrix (U). This method is particularly useful for solving large systems of linear equations.

4.1 What is LU Decomposition?

LU decomposition expresses a matrix $\mathbf{A}$ as the product:

$$\mathbf{A} = \mathbf{L} \mathbf{U}$$

where $\mathbf{L}$ is a lower triangular matrix and $\mathbf{U}$ is an upper triangular matrix.

4.2 Solving Systems Using LU Decomposition

To solve the system $\mathbf{A} \mathbf{x} = \mathbf{b}$:

1. Decompose $\mathbf{A}$ into $\mathbf{L}$ and $\mathbf{U}$: Find matrices $\mathbf{L}$ and $\mathbf{U}$ such that $\mathbf{A} = \mathbf{L} \mathbf{U}$.
2. Solve $\mathbf{L} \mathbf{y} = \mathbf{b}$: Solve for $\mathbf{y}$ using forward substitution.
3. Solve $\mathbf{U} \mathbf{x} = \mathbf{y}$: Solve for $\mathbf{x}$ using back substitution.

4.3 Example

Given the matrix $\mathbf{A}$ and vector $\mathbf{b}$:

$$\mathbf{A} = \begin{pmatrix} 4 & 3 \\ 6 & 3 \end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} 10 \\ 12 \end{pmatrix}$$

Decompose $\mathbf{A}$ into $\mathbf{L}$ and $\mathbf{U}$:

$$\mathbf{L} = \begin{pmatrix} 1 & 0 \\ 1.5 & 1 \end{pmatrix}, \quad \mathbf{U} = \begin{pmatrix} 4 & 3 \\ 0 & -1.5 \end{pmatrix}$$

Now solve $\mathbf{L} \mathbf{y} = \mathbf{b}$ and then $\mathbf{U} \mathbf{x} = \mathbf{y}$ to find the solution $\mathbf{x}$.

---

Conclusion

Solving systems of linear equations is a critical skill in linear algebra, with applications in various fields. Whether using simple methods like substitution and elimination or more advanced techniques like Gaussian elimination and LU decomposition, understanding these methods provides a foundation for tackling more complex problems in mathematics, science, and engineering.