Linear Algebra

1.2 Gaussian Elimination

Imron Rosyadi

Introduction to Gaussian Elimination

In the previous section, we saw how elementary row operations can transform a linear system’s augmented matrix into a simpler form from which solutions are evident. This section formalizes that process.

We will cover:

• Defining Row Echelon Form (REF) and Reduced Row Echelon Form (RREF).
• Interpreting solutions from REF/RREF matrices.
• The systematic procedures: Gaussian Elimination and Gauss-Jordan Elimination.
• Special considerations for homogeneous linear systems.

Good morning, everyone! Today, we delve deeper into solving linear systems, moving beyond ad-hoc elimination to a systematic, algorithmic approach. This is where linear algebra truly shines, providing robust methods that are essential for both manual calculations and, more importantly, for computational solutions in engineering.

Many real-world engineering problems involve systems with thousands or even millions of unknowns, far too large to solve by hand. The concepts we’ll discuss today are the foundation of the numerical algorithms used in computer software for these massive systems, even with considerations like memory and roundoff errors. Understanding these procedures is crucial for any ECE student. Let’s define the formal forms matrices take and the steps to achieve them.

Echelon Forms of Matrices

A matrix is in Row Echelon Form (REF) if it has the following properties:

1. If a row doesn’t consist entirely of zeros, its first nonzero number (called a leading 1) is 1.
2. Any rows consisting entirely of zeros are grouped at the bottom.
3. In any two successive non-zero rows, the leading 1 in the lower row is farther to the right than the leading 1 in the higher row.

A matrix in Reduced Row Echelon Form (RREF) has all three REF properties, plus:

4. Each column containing a leading 1 has zeros everywhere else in that column (above and below the leading 1).

The goal of our systematic procedures is to transform any augmented matrix into one of these specific “echelon forms.” These forms simplify the interpretation of solutions.

Think of “echelon” like steps or a staircase. * Leading 1: This is our pivot element, the first non-zero entry in a non-zero row, and we make it 1. * Zero rows at bottom: This isolates trivial equations (0=0). * Staircase pattern: The leading 1s move progressively to the right, creating a clear structure. * Zeros below leading 1s (REF): This is the “staircase” effect. For example, once the first element of the first row is a leading 1, you can use it to zero out all elements below it in that column. * Zeros above AND below leading 1s (RREF): This is stricter. Not only are zeros below a leading 1, but also above it in the same column. Once a matrix is in RREF, the solution can often be directly read from the augmented matrix, or derived with minimal effort. Example 6 from our last lecture was a perfect example of a matrix in RREF.

Example 1: Row Echelon vs. Reduced Row Echelon Forms

Reduced Row Echelon Form Examples: (All follow properties 1-4) \[ \left[{\begin{array}{r r r | r}{1}&{0}&{0}&{4}\\ {0}&{1}&{0}&{7}\\ {0}&{0}&{1}&{-1}\end{array}}\right] \] \[ \left[{\begin{array}{r r r}{1}&{0}&{0}\\ {0}&{1}&{0}\\ {0}&{0}&{1}\end{array}}\right] \] \[ \left[{\begin{array}{r r r r | r}{0}&{1}&{-2}&{0}&{1}\\ {0}&{0}&{0}&{1}&{3}\\ {0}&{0}&{0}&{0}&{0}\\ {0}&{0}&{0}&{0}&{0}\end{array}}\right] \]

Row Echelon Form Examples (NOT Reduced): (Follow properties 1-3, but NOT 4) \[ \left[{\begin{array}{r r r | r}{1}&{4}&{-3}&{7}\\ {0}&{1}&{6}&{2}\\ {0}&{0}&{1}&{5}\end{array}}\right] \]

\[ \left[{\begin{array}{r r r}{1}&{1}&{0}\\ {0}&{1}&{0}\\ {0}&{0}&{0}\end{array}}\right] \]

\[ \left[{\begin{array}{r r r r | r}{0}&{1}&{2}&{6}&{0}\\ {0}&{0}&{1}&{-1}&{0}\\ {0}&{0}&{0}&{0}&{1}\end{array}}\right] \]

Let’s look at concrete examples of these forms. On the left, you see matrices in Reduced Row Echelon Form. Observe that in any column where there’s a leading 1 (the first non-zero entry in its row), all other entries in that column are zero. This is the defining characteristic of RREF. It looks like an identity matrix (or part of one) with zeros around the leading 1s.

On the right, these matrices are in Row Echelon Form but not Reduced Row Echelon Form. They have leading 1s, the staircase pattern, and zero rows at the bottom (if any). However, they also have non-zero entries above the leading 1s. For example, in the first matrix on the right, the 4, -3, and 7 in the first row are above leading 1s. While these are perfectly valid REF matrices, they require a bit more work (back-substitution) to get the final solution. The goal of Gauss-Jordan is to reach the RREF, which gives the solution directly.

Solving Systems from Echelon Forms

Once an augmented matrix is in REF or RREF, the solution to the linear system can be obtained.

Example 3: Unique Solution (From RREF)

Suppose RREF of augmented matrix for \(x_1, x_2, x_3, x_4\) is: \[ \left[{\begin{array}{c c c c | c}{1}&{0}&{0}&{0}&{3}\\ {0}&{1}&{0}&{0}&{-1}\\ {0}&{0}&{1}&{0}&{0}\\ {0}&{0}&{0}&{1}&{5}\end{array}}\right] \] This directly translates to: \[ x_1 = 3, \quad x_2 = -1, \quad x_3 = 0, \quad x_4 = 5 \] This is a unique solution.

The power of echelon forms lies in how easily we can extract the solutions. When the augmented matrix is in Reduced Row Echelon Form, especially like this example, reading the solution is instantaneous. The left side of the augmented matrix resembles an identity matrix, meaning each variable is isolated. We can simply read off the values from the rightmost column. This tells us there is exactly one solution.

Solving Systems from Echelon Forms (Cont.)

Example 4(a): No Solution

Suppose RREF of augmented matrix for \(x, y, z\) is: \[ \left[{\begin{array}{l l l | l}{1}&{0}&{0}&{0}\\ {0}&{1}&{2}&{0}\\ {0}&{0}&{0}&{1}\end{array}}\right] \] The last row corresponds to the equation: \[ 0x + 0y + 0z = 1 \implies 0=1 \] This is a contradiction. The system is inconsistent and has no solution.

Not all linear systems have solutions. When you convert an augmented matrix to RREF and encounter a row like this, it immediately tells you the system is inconsistent. The row [0 0 0 | 1] translates to \(0x + 0y + 0z = 1\), or simply \(0=1\). This is logically impossible. Therefore, no values of \(x, y, z\) can satisfy this equation, meaning no solution exists for the entire system.

Solving Systems from Echelon Forms (Cont.)

Example 4(b): Infinitely Many Solutions

Suppose RREF of augmented matrix for \(x, y, z\) is: \[ \left[{\begin{array}{l l l | l}{1}&{0}&{3}&{-1}\\ {0}&{1}&{-4}&{2}\\ {0}&{0}&{0}&{0}\end{array}}\right] \] The last row \(0=0\) can be omitted. The corresponding system is: \[ \begin{array}{r}x + 3z = -1 \\ y - 4z = 2 \end{array} \] Variables corresponding to leading 1s (\(x, y\)) are leading variables. Others (\(z\)) are free variables. Solve for leading variables in terms of free variables: \[ \begin{array}{l}x = -1 - 3z \\ y = 2 + 4z \end{array} \] Assign an arbitrary value (parameter) \(t\) to the free variable \(z\). The general solution (parametric equations) is: \[ x = -1 - 3t, \quad y = 2 + 4t, \quad z = t \] Specific solutions can be found by choosing values for \(t\). For example, if \(t=0\), then \((x,y,z)=(-1,2,0)\). If \(t=1\), then \((x,y,z)=(-4,6,1)\).

This scenario leads to infinitely many solutions, as we discussed in the previous lecture. When the RREF contains a row of all zeros for coefficients (like [0 0 0 | 0]), it means that equation provides no new information. It’s simply \(0=0\).

In this example, \(x\) and \(y\) are our leading variables because they correspond to the columns with leading 1s. \(z\) is a free variable because it does not have a leading 1 in its column. Free variables can take any arbitrary real value.

To represent all infinitely many solutions, we express the leading variables in terms of the free variables. By introducing a parameter, say \(t\), for the free variable \(z\), we obtain parametric equations. These equations form what’s called a general solution because by varying the parameter \(t\), you can generate every possible solution to the system. This method is common in control and signal processing, where you might have underdetermined systems.

Solving Systems from Echelon Forms (Cont.)

Example 4(c): Infinitely Many Solutions (Another form)

Suppose RREF of augmented matrix for \(x, y, z\) is: \[ \left[{\begin{array}{l l l | l}{1}&{-5}&{1}&{4}\\ {0}&{0}&{0}&{0}\\ {0}&{0}&{0}&{0}\end{array}}\right] \] The system reduces to a single equation: \[ x - 5y + z = 4 \] Here, \(x\) is the only leading variable. \(y\) and \(z\) are free variables. Let \(y = s\) and \(z = t\) (parameters). Then \(x = 4 + 5y - z \implies x = 4 + 5s - t\).

The general solution is: \[ x = 4 + 5s - t, \quad y = s, \quad z = t \] This represents a plane in 3D space.

Here’s another case of infinitely many solutions. This time, after reduction, we’re left with only one non-zero row. The rest are zero rows, offering no information.

This means we have only one effective equation: \(x - 5y + z = 4\). With three unknowns and only one equation, we have degrees of freedom. \(x\) is the leading variable here. Both \(y\) and \(z\) are free variables, allowing us to assign them arbitrary parameters, \(s\) and \(t\).

This again results in a parametric solution, but with two parameters, because the solution set is a plane in three-dimensional space, which requires two dimensions (or two parameters) to describe. This type of solution arises in engineering when systems are flexible or when there are more variables than independent constraints, such as in process control optimization.

Gauss-Jordan Elimination: Step-by-Step Procedure

This algorithm reduces any matrix to its unique Reduced Row Echelon Form.

Phase 1: Forward Elimination (Gaussian Elimination to REF) Goal: Create leading 1s and zeros below them.

1. Locate Leftmost Non-Zero Column: This will be your first pivot column.
2. Move Non-Zero Entry to Top: If needed, interchange the top row with another row to get a non-zero entry at the top of the pivot column.
3. Create Leading 1: Multiply the top row by the reciprocal of its new leading entry to make it 1.
4. Create Zeros Below Leading 1: Add suitable multiples of the new first row to rows below it to make all entries below the leading 1 zero.
5. Repeat for Submatrix: Cover the top row and repeat steps 1-4 on the remaining (sub)matrix. Continue until the entire matrix is in Row Echelon Form.

Gauss-Jordan Elimination: Step-by-Step Procedure

Phase 2: Backward Elimination (To RREF) Goal: Create zeros above the leading 1s.

6. Create Zeros Above Leading 1s: Starting with the last non-zero row and working upwards, add suitable multiples of each row to the rows above to introduce zeros above the leading 1s.

The final matrix is in Reduced Row Echelon Form.

Now that we understand what REF and RREF are, let’s learn the systematic procedure to achieve them. This two-phase algorithm is called Gauss-Jordan elimination.

The first phase, Forward Elimination, is essentially what’s known as Gaussian Elimination. Its objective is to transform the matrix into Row Echelon Form. You identify the leftmost column that isn’t all zeros – this is your “pivot” column for that step. You then ensure a non-zero entry is at the top of this column, make it a “leading 1” by scaling the row, and then use that leading 1 to “zero out” all the entries directly below it. You then ignore this processed row and column and repeat the process on the remaining “submatrix”. This process continues until you have the staircase-like REF structure, with all zeros below the leading 1s.

The second phase, Backward Elimination, is what distinguishes Gauss-Jordan from just Gaussian Elimination. Once in REF, you work upwards from the last leading 1. You use this leading 1 to zero out any non-zero entries above it in its column. You repeat this for all leading 1s until all entries above and below them are zero. The result is the cleaner, reduced row echelon form. This systematic process is what computers execute to solve large-scale linear systems.

Interactive Example: Gauss-Jordan Elimination

Let’s apply Gauss-Jordan Elimination to the augmented matrix for the system: \(x + y + 2z = 9\)
\(2x + 4y - 3z = 1\)
\(3x + 6y - 5z = 0\)

Initial Augmented Matrix: \[ \left[ \begin{array}{r r r | r}{1} & 1 & 2 & 9\\ {2} & 4 & {-3} & 1\\ {3} & 6 & {-5} & 0 \end{array} \right] \]

Interactive Example: Gauss-Jordan Elimination

Let’s see the Gauss-Jordan process in action using a simple Python script in Pyodide. This code block will perform the exact elementary row operations we discussed and show the matrix transformation at each step.

You can click on the ‘Show Code’ button to see how these operations are implemented using NumPy arrays. Notice how each step carefully targets one position to become zero or one.

• Steps 1-4 correspond to the forward elimination phase, bringing the matrix to Row Echelon Form.
• Steps 5-8 correspond to the backward elimination phase, bringing it to Reduced Row Echelon Form.

The final matrix is [[1. 0. 0. 1.], [0. 1. 0. 2.], [0. 0. 1. 3.]]. This directly implies \(x=1, y=2, z=3\), demonstrating the power of Gauss-Jordan elimination for direct solution retrieval. This method is the basis for many numerical linear algebra libraries used in engineering software, where speed and accuracy are paramount.

Interactive: Reduced Row Echelon Form Calculator

Homogeneous Linear Systems

A system of linear equations is homogeneous if all constant terms are zero: \[ \begin{array}{r l} a_{11}x_{1} + \dots +a_{1n}x_{n} &= 0\\ a_{21}x_{1} + \dots +a_{2n}x_{n} &= 0\\ \vdots\qquad\vdots\qquad\vdots\qquad\vdots \\ a_{m1}x_{1} + \dots +a_{mn}x_{n} &= 0 \end{array} \]

Homogeneous Linear Systems

Key properties of homogeneous systems:

• Always consistent: \(x_1=0, x_2=0, \ldots, x_n=0\) is always a solution (the trivial solution).
• Can have only two types of solutions:
  1. Only the trivial solution.
  2. Infinitely many solutions (including the trivial solution, which are then called nontrivial solutions).

Homogeneous Linear Systems

Geometrically: For 2D, lines pass through the origin. If they’re distinct and intersect only at origin \(\implies\) trivial solution. If they coincide \(\implies\) infinitely many solutions.

Homogeneous System Geometry

Homogeneous linear systems are a special but incredibly important class of linear systems. They are defined by having all zeros on the right-hand side of the equations.

A critical property is that they are always consistent. This is because \(x_1=0, x_2=0, \ldots, x_n=0\) (the trivial solution) will always satisfy every equation. If adding more variables or equations results in having actual non-zero solutions, these are called nontrivial solutions.

Geometrically, in 2D, homogeneous equations represent lines passing through the origin \((0,0)\). The trivial solution corresponds to the origin itself. If the lines are distinct, they only intersect at the origin (unique trivial solution). If they are the same line, they have infinitely many solutions (all points on the line, including the origin). These systems appear often in physical modeling; for example, determining if there are non-zero currents in a circuit without any external voltage sources applied.

Homogeneous Linear Systems (Cont.)

Theorem 1.2.1: Free Variable Theorem for Homogeneous Systems

If a homogeneous linear system has \(n\) unknowns, and if the reduced row echelon form of its augmented matrix has \(r\) nonzero rows, then the system has \(n - r\) free variables.

Theorem 1.2.2: Existence of Nontrivial Solutions

A homogeneous linear system with more unknowns than equations (i.e., \(n > m\)) has infinitely many solutions.

• Proof Sketch: If \(m < n\) (equations < unknowns), then when reducing to RREF, the number of leading 1s (\(r\)) must be less than or equal to \(m\). So, \(r \le m < n\). This means \(n - r > 0\), guaranteeing at least one free variable. Since free variables can take infinite values, there are infinitely many solutions (including the trivial one).

This theorem is very powerful and has applications in fields like signal processing (e.g., finding the null space of a matrix where the outputs of a system are zero) and control theory (e.g., determining system stability).

These two theorems are cornerstone results for homogeneous systems.

Theorem 1.2.1 tells us exactly how many free variables we’ll have. Each non-zero row in the RREF gives us a leading variable. The remaining variables are free. So, if you have \(n\) unknowns and \(r\) leading variables (which is the number of non-zero rows), you’ll have \(n-r\) free variables. This is a direct measure of the “degree of freedom” in your solution set.

Theorem 1.2.2 is a very practical shortcut. It says that if you have fewer equations than unknowns in a homogeneous system, you are guaranteed to have infinitely many solutions. This is because you won’t have enough independent constraints to pin down all your variables to unique values. In an ECE context, this might occur when you’re analyzing a network, and you have more unknown currents than independent Kirchhoff’s Current Law junctions or Kirchhoff’s Voltage Law loops, implying multiple current distributions can satisfy the zero-source conditions.

Example 6: A Homogeneous System

Solve the homogeneous linear system: \[ \begin{array}{r r r r r r} {x_{1} + 3x_{2}} & {-2x_{3}} & {} & {+2x_{5}} & {} & = 0\\ {2x_{1} + 6x_{2}} & {-5x_{3}} & {-2x_{4}} & {+4x_{5}} & {- 3x_{6}} & = 0\\ {} & {5x_{3}} & {+10x_{4}} & {} & {+15x_{6}} & = 0\\ {2x_{1} + 6x_{2}} & {} & {+8x_{4}} & {+4x_{5}} & {+18x_{6}} & = 0 \end{array} \] This is the same system as in Example 5, but with zeros on the right-hand side. The augmented matrix is: \[ \left[{\begin{array}{r r r r r r | r}{1}&{3}&{-2}&{0}&{2}&{0}&{0}\\ {2}&{6}&{-5}&{-2}&{4}&{-3}&{0}\\ {0}&{0}&{5}&{10}&{0}&{15}&{0}\\ {2}&{6}&{0}&{8}&{4}&{18}&{0}\end{array}}\right] \] Note that elementary row operations will preserve the column of zeros.

Example 6: A Homogeneous System

Its RREF (from Example 5’s reduction) will be: \[ \left[{\begin{array}{r r r r r r | r}{1}&{3}&{0}&{4}&{2}&{0}&{0}\\ {0}&{0}&{1}&{2}&{0}&{0}&{0}\\ {0}&{0}&{0}&{0}&{0}&{1}&{0}\\ {0}&{0}&{0}&{0}&{0}&{0}&{0}\end{array}}\right] \] The corresponding system of equations is: \[ \begin{array}{r r r r r r} {x_{1} + 3x_{2}} & {} & {+4x_{4}} & {+ 2x_{5}} & {} & {= 0}\\ {} & {x_{3}} & {+2x_{4}} & {} & {} & {= 0}\\ {} & {} & {} & {} & {x_{6}} & {= 0} \end{array} \] Leading variables: \(x_1, x_3, x_6\). Free variables: \(x_2, x_4, x_5\). Let \(x_2 = r, x_4 = s, x_5 = t\). Solution: \[ x_{1} = -3r - 4s - 2t, \quad x_{2} = r, \quad x_{3} = -2s, \quad x_{4} = s, \quad x_{5} = t, \quad x_{6} = 0 \] Since there are free variables, this homogeneous system has infinitely many solutions. The trivial solution is when \(r=s=t=0\).

We use the same matrix transformation as in Example 5 because the coefficients are identical, and the right-hand side, being all zeros, will remain all zeros throughout the elementary row operations. This is a very convenient property of homogeneous systems.

From the RREF, we identify our leading variables (\(x_1, x_3, x_6\)) and our free variables (\(x_2, x_4, x_5\)). Here, we have \(n=6\) unknowns and \(r=3\) non-zero rows, so we have \(n-r = 6-3=3\) free variables, as per Theorem 1.2.1. This directly tells us we will have infinitely many solutions, including the trivial solution when all parameters are zero.

This example ties directly into the concept of a matrix’s null space (or kernel) - the set of all vectors that are mapped to the zero vector by the linear transformation defined by the matrix. Finding the null space involves solving just such a homogeneous system, a common task in image processing, machine learning, and control theory.

Gaussian Elimination and Back-Substitution

For computer-based solutions of large systems, Gaussian Elimination (reducing to Row Echelon Form) followed by back-substitution is generally more efficient than full Gauss-Jordan elimination.

Procedure:

1. Use elementary row operations to reduce the augmented matrix to Row Echelon Form (REF) (Forward Elimination).
2. Write the corresponding system of equations.
3. Solve the equations for the leading variables.
4. Starting from the bottom equation and working upwards, substitute the values of determined variables (or parametric expressions) into the equations above.
5. Assign arbitrary values to any remaining free variables to get the general solution.

Gaussian Elimination and Back-Substitution

Example 7: Example 5 Solved by Back-Substitution

REF from Example 5: \[ \left[{\begin{array}{r r r r r r | r}{1}&{3}&{-2}&{0}&{2}&{0}&{0}\\ {0}&{0}&{1}&{2}&{0}&{3}&{1}\\ {0}&{0}&{0}&{0}&{0}&{1}&{{\frac{1}{3}}}\\ {0}&{0}&{0}&{0}&{0}&{0}&{0}\end{array}}\right] \] Corresponding system: \[ \begin{array}{l} x_1 + 3x_2 - 2x_3 + 2x_5 = 0 \\ x_3 + 2x_4 + 3x_6 = 1 \\ x_6 = \frac{1}{3} \end{array} \] Solving for leading variables (\(x_1, x_3, x_6\)): \[ \begin{array}{l} {x_1 = -3x_2 + 2x_3 - 2x_5} \\ {x_3 = 1 - 2x_4 - 3x_6} \\ {x_6 = \frac{1}{3}} \end{array} \]

Gaussian Elimination and Back-Substitution

Now, back-substitute:

1. Substitute \(x_6 = \frac{1}{3}\) into the second equation: \(x_3 = 1 - 2x_4 - 3\left(\frac{1}{3}\right) \implies x_3 = 1 - 2x_4 - 1 \implies x_3 = -2x_4\)
2. Substitute \(x_3 = -2x_4\) into the first equation: \(x_1 = -3x_2 + 2(-2x_4) - 2x_5 \implies x_1 = -3x_2 - 4x_4 - 2x_5\)

Assign free variables \(x_2=r, x_4=s, x_5=t\). Resulting general solution: \[ x_1 = -3r - 4s - 2t, \quad x_2 = r, \quad x_3 = -2s, \quad x_4 = s, \quad x_5 = t, \quad x_6 = \frac{1}{3} \] This confirms the same solution as Gauss-Jordan elimination for Example 5.

While Gauss-Jordan gives the direct solution in RREF, for very large systems, the “backward elimination” phase (making zeros above leading 1s) is computationally more expensive than simply using back-substitution. That’s why Gaussian Elimination (to REF) followed by back-substitution is preferred for computational efficiency.

Let’s revisit Example 5 with this method. We already have the REF from our previous steps. Now, convert it back into equations. The key here is the back-substitution part. You start from the bottommost equation that provides a direct value (like \(x_6 = 1/3\)). You substitute this value into the equation above it, then solve for the next leading variable. You continue this upward process, substituting known values (or expressions in terms of free variables) into higher equations, until all leading variables are expressed either as unique numerical values or in terms of the free variables.

The final parametric solution is identical to what we got with Gauss-Jordan, demonstrating that both methods yield the same correct result, but Gaussian elimination + back-substitution can be more efficient for computers. This process is fundamental to how linear system solvers work in tools like MATLAB, SciPy, and other numerical analysis packages crucial for ECE applications.

Example 8: Discussion on Solutions from REF

Suppose these are augmented matrices for systems in \(x_1, x_2, x_3, x_4\). All are in REF, but not RREF.

(a) No Solution \[ {\left[\begin{array}{l l l l | l}{1}&{-3}&{7}&{2}&{5}\\ {0}&{1}&{2}&{-4}&{1}\\ {0}&{0}&{1}&{6}&{9}\\ {0}&{0}&{0}&{0}&{1}\end{array}\right]} \] Last row: \(0=1\). Inconsistent.

(b) Infinitely Many Solutions \[ {\left[\begin{array}{l l l l | l}{1}&{-3}&{7}&{2}&{5}\\ {0}&{1}&{2}&{-4}&{1}\\ {0}&{0}&{1}&{6}&{9}\\ {0}&{0}&{0}&{0}&{0}\end{array}\right]} \] Last row: \(0=0\). Leading variables \(x_1, x_2, x_3\). Free variable \(x_4\). Infinitely many solutions.

Example 8: Discussion on Solutions from REF

(c) Unique Solution \[ {\left[\begin{array}{l l l l | l}{1}&{-3}&{7}&{2}&{5}\\ {0}&{1}&{2}&{-4}&{1}\\ {0}&{0}&{1}&{6}&{9}\\ {0}&{0}&{0}&{1}&{0}\end{array}\right]} \] Last row: \(x_4=0\). All variables are leading variables. Unique solution.

These examples (a), (b), and (c) reinforce how to interpret solutions directly from a matrix in Row Echelon Form.

• (a) No Solution: As before, a row of [0 0 0 0 | 1] or similar directly means inconsistency. This is a common situation for engineers where your model assumptions might be contradictory, leading to no possible physical solution.
• (b) Infinitely Many Solutions: A row of all zeros (including the constant term) means that equation is redundant. If you have fewer leading 1s than variables (i.e., you have free variables), you will have infinite solutions. This suggests flexibility in a system or potentially an underdefined problem.
• (c) Unique Solution: If every variable corresponds to a leading 1 (no free variables), and there are no contradictory rows, you will have a unique solution. Even though the matrix isn’t fully reduced, you can still determine uniqueness by counting leading 1’s. This often represents tightly constrained, well-defined problems where there’s only one way for the system to behave.

These insights are crucial for diagnosing circuit behaviors, analyzing control system stability, or simulating physical phenomena in engineering.

Important Facts About Echelon Forms

1. Unique RREF: Every matrix has a unique reduced row echelon form. No matter what sequence of elementary row operations you use, you will always arrive at the same RREF for a given matrix.
2. Non-Unique REF: Row echelon forms (REF) are not unique. Different sequences of elementary row operations can lead to different REF forms for the same matrix.
3. Pivot Positions/Columns are Unique: Although REF can vary, the number of zero rows and the positions of the leading 1s (called pivot positions) are always the same for a given matrix. Columns containing pivot positions are called pivot columns.

Important Facts About Echelon Forms

Example 9: Pivot Positions and Columns

For the matrix \[ A = \begin{bmatrix} 0 & 0 & -2 & 0 & 7 & 12 \\ 2 & 4 & -10 & 6 & 12 & 28 \\ 2 & 4 & -5 & 6 & -5 & -1 \end{bmatrix} \] one possible REF is: \[ \left[ \begin{array}{cccccc}1 & 2 & -5 & 3 & 6 & 14 \\ 0 & 0 & 1 & 0 & -\frac{7}{2} & -6 \\ 0 & 0 & 0 & 0 & 1 & 2 \end{array} \right] \] The leading 1s are in positions (row 1, column 1), (row 2, column 3), and (row 3, column 5). These are the pivot positions. The pivot columns are columns 1, 3, and 5. In a linear system, pivot columns identify the leading variables. Here, \(x_1, x_3, x_5\) would be leading variables.

Before we conclude, let’s highlight some critical theoretical properties of echelon forms that are important in advanced linear algebra and numerical analysis.

1. Uniqueness of RREF: This is a very powerful guarantee. It means that regardless of the path you take with elementary row operations, if you reduce a matrix all the way to RREF, you will always get the same final matrix. This provides a definitive “canonical form” for any given matrix.
2. Non-Uniqueness of REF: In contrast, there can be multiple valid Row Echelon Forms for a single matrix. This is because the choices of row operations in the forward phase can sometimes be arbitrary.
3. Uniqueness of Pivot Positions: Despite the non-uniqueness of REF, the locations of the leading 1s (the pivot positions) are always fixed. This means the number of leading variables and the specific variables that are leading (the pivot columns) are invariant properties of the matrix. This is a crucial concept for understanding matrix rank, which we’ll cover later, and for identifying independent variables in engineering models.

For instance, in the example, columns 1, 3, and 5 are pivot columns. This immediately tells us that if this were an augmented matrix for a system with variables \(x_1, \ldots, x_5\), then \(x_1, x_3, x_5\) would be our leading variables. Understanding pivot columns is vital in fields like data compression and feature selection in machine learning, which heavily rely on linear algebra.

Roundoff Error and Stability

While Gaussian and Gauss-Jordan elimination are mathematically sound, their practical implementation on computers faces challenges:

• Roundoff Errors: Computers use finite-precision arithmetic, leading to small errors in calculations.
• Instability: Successive calculations can amplify these roundoff errors, rendering results inaccurate or “unstable.”

For large systems (e.g., in computational fluid dynamics, large-scale circuit simulations), specialized numerical techniques are used to minimize these errors. Gaussian elimination is generally preferred over Gauss-Jordan due to fewer operations, reducing error propagation.

Finally, a quick but important note for future ECE endeavors. While we’ve learned the exact mathematical procedures for solving linear systems, real-world computations using computers introduce complexities.

Computers can only represent numbers with a finite number of decimal places. This “roundoff” can introduce tiny errors. When you perform millions of elementary row operations on a large matrix, these tiny errors can accumulate and, in some cases, magnify, leading to a completely incorrect answer. An algorithm that is susceptible to this error magnification is called “unstable.”

Therefore, numerical linear algebra, a specialized field, focuses on developing “stable” algorithms that minimize roundoff error. It’s why engineers often use pre-built, robust libraries (like NumPy’s linear algebra functions) instead of coding these algorithms from scratch, as these libraries employ sophisticated techniques to manage these numerical challenges. Gaussian elimination is often favored over Gauss-Jordan in these libraries because it generally involves fewer arithmetic operations, thus less opportunity for error accumulation.

Conclusion

• Echelon Forms (REF & RREF): Provide structured representations of matrices for systematic problem-solving.
• Gaussian Elimination & Gauss-Jordan Elimination: Algorithms for transforming matrices into echelon forms.
• Solutions: Determined by the final echelon form (unique, infinite, or no solution).
• Homogeneous Systems: Always consistent, trivial solution always exists, nontrivial solutions if free variables exist.
• Practical Importance: These methods are fundamental to numerical algorithms for systems of equations in all ECE applications, from circuit analysis to control systems, signal processing, and machine learning.

To conclude our discussion on Gaussian Elimination: We’ve defined the two critical forms matrices can take: Row Echelon Form and Reduced Row Echelon Form, understanding their properties and how they differ. We’ve learned the step-by-step algorithms, Gauss-Jordan and Gaussian elimination with back-substitution, for achieving these forms. We’ve reviewed how to interpret the solution types (unique, infinite, no solution) directly from the echelon forms. And we covered homogeneous systems, a special class that always has at least the trivial solution, with the key insight that more unknowns than equations guarantees infinitely many solutions.

The systematic approach of Gaussian and Gauss-Jordan elimination is not just an academic exercise. It is the bedrock of how computers solve linear systems efficiently and accurately. Whether you’re analyzing the behavior of op-amp circuits, designing digital filters, or optimizing power grids, you will encounter linear systems, and these methods are the backbone of their solutions.

Next time, we will explore vectors and their properties, building further on these foundational concepts. Thank you!

Exercises

grasple_exercise_2_1_B

To perform row operations on a matrix.

Exercises

grasple_exercise_2_1_C

Checking whether a matrix is in (reduced) echelon form.

Exercises

grasple_exercise_2_1_E

Applying the algorithm to compute a solution of a linear system.