Linear Algebra

1.5 Elementary Matrices and a Method for Finding \(A^{-1}\)

Imron Rosyadi

Linear Algebra in ECE

1.5 Elementary Matrices and a Method for Finding \(A^{-1}\)

Imron Rosyadi

An essential tool for understanding and solving linear systems in engineering.

Good morning everyone! Today, we’re diving into a crucial topic in linear algebra: elementary matrices and how they help us find the inverse of a matrix. This might sound abstract, but it’s fundamental to many areas in Electrical and Computer Engineering, from circuit analysis to signal processing and control systems. We’ll explore the theoretical underpinnings and practical computational methods.

Moment of Silence

1D elastic collision

A mass \(M1\) (moving) with initial velocity \(U_1\) hits another mass \(m_2\) that is initially at rest. We assume a perfectly elastic collision in one dimension. Unknown final velocities are:

• \(V_1\) — final velocity of mass \(M1\),
• \(v_2\) — final velocity of mass \(m2\).

Two equations govern the collision:

1. Conservation of linear momentum

\[ M_1 U_1 = M_1 V_1 + m_2 v_2 \]

2. Elastic collision condition (relative velocity reversal)

\[ V_1 - v_2 = -(U_1 - 0) = -U_1 \]

Rewrite as a linear system \(A\mathbf{x}=\mathbf{b}\) with \(\mathbf{x}=[V_1,\,v_2]^\top\):

\[ \begin{bmatrix} M_1 & m_2 \\[4pt] 1 & -1 \end{bmatrix} \begin{bmatrix} V_1 \\ v_2 \end{bmatrix} = \begin{bmatrix} M_1 U_1 \\ -U_1 \end{bmatrix}. \]

Linear Algebra in ECE

1.5 Elementary Matrices and a Method for Finding \(A^{-1}\)

Introduction: Why Elementary Matrices?

• How do we systematically find the inverse of a matrix?
• How do basic row operations relate to matrix multiplication?

In this section, we’ll develop an algorithm for finding the inverse of a matrix and discuss key properties of invertible matrices. We’ll start by revisiting elementary row operations.

We’ve touched upon matrix inverses before, but how do we actually compute them for larger matrices systematically? And how do the basic row operations that we’ve been using, like scaling a row or swapping rows, relate to matrix multiplication? These are the questions we’ll answer today. Understanding this connection is key, as it provides a powerful framework for matrix manipulation and solving linear systems.

Elementary Row Operations

Recall the three elementary row operations on a matrix \(A\):

1. Scaling: Multiply a row by a nonzero constant \(c\).
   • Inverse Operation: Multiply the same row by \(1/c\).
2. Interchange: Interchange two rows.
   • Inverse Operation: Interchange the same two rows.
3. Replacement: Add a constant \(c\) times one row to another.
   • Inverse Operation: Add \(-c\) times the same row to the other.

Remember these operations from Section 1.1? They are the fundamental tools for Gaussian elimination and Gauss-Jordan elimination. It’s important to note that each of these operations is reversible. If you perform an operation, you can always undo it with a corresponding inverse operation. This concept of reversibility is crucial when we talk about matrix inverses.

Row Equivalence & Elementary Matrices

DEFINITION 1: Row Equivalence
Matrices \(A\) and \(B\) are row equivalent if either (hence each) can be obtained from the other by a sequence of elementary row operations.

DEFINITION 2: Elementary Matrix
A matrix \(E\) is called an elementary matrix if it can be obtained from an identity matrix by performing a single elementary row operation.

These two definitions are foundational for today’s topic. Row equivalence establishes a relationship between matrices that can be transformed into one another using elementary row operations. The concept of an “elementary matrix” is where things get interesting: it’s a matrix that represents a single elementary row operation.

Example 1: Elementary Matrices

Listed below are four elementary matrices and the operations that produce them from an identity matrix \(I\).

Here you can see concrete examples. The first matrix on the left is formed by multiplying the second row of \(I_3\) by 7. The second, by swapping the first and third rows of \(I_3\). The third, by adding -2 times the first row to the third row of \(I_3\). And the fourth, by multiplying the first row of \(I_2\) by 1. Notice how they all originate from an identity matrix and correspond to one specific elementary row operation.

Theorem 1.5.1: Row Operations by Matrix Multiplication

If the elementary matrix \(E\) results from performing a certain row operation on \(I_m\) and if \(A\) is an \(m \times n\) matrix, then the product \(EA\) is the matrix that results when this same row operation is performed on \(A\).

This is a powerful result: performing a row operation on \(A\) is equivalent to multiplying \(A\) by an elementary matrix from the left.

This theorem is a game-changer. It means that seemingly simple row operations, which we’ve performed directly on matrices, can actually be represented as matrix multiplications. This connection is super important because it allows us to analyze complicated sequences of row operations using the algebra of matrices. Later, we will see how this concept has profound implications for understanding matrix invertibility and factorization in signal processing or control systems.

Example 2: Using Elementary Matrices

Consider the matrix: \[ A = \left[ \begin{array}{rrrr}1 & 0 & 2 & 3 \\ 2 & -1 & 3 & 6 \\ 1 & 4 & 4 & 0 \end{array} \right] \]

And the elementary matrix: \[ E = \left[ \begin{array}{lll}1 & 0 & 0 \\ 0 & 1 & 0 \\ 3 & 0 & 1 \end{array} \right] \]

\(E\) results from adding 3 times the first row of \(I_3\) to its third row.

The product \(EA\) is:

\[ EA = \left[ \begin{array}{rrrr}1 & 0 & 2 & 3 \\ 2 & -1 & 3 & 6 \\ 4 & 4 & 10 & 9 \end{array} \right] \]

This is precisely what you get by adding 3 times row 1 of \(A\) to row 3 of \(A\).

Let’s see this in action. We have matrix A and elementary matrix E. E was formed by taking I3 and adding 3 times its first row to its third row. Now, if we explicitly multiply E by A, we get a new matrix. If you look closely, you’ll see that this new matrix is exactly what you would get if you performed that same row operation (add 3 times row 1 to row 3) directly on matrix A. This example beautifully illustrates Theorem 1.5.1. While we often perform row operations directly in practice, understanding this matrix multiplication equivalent is crucial for theoretical proofs and more advanced matrix decompositions.

Example 2: Python Demonstration

Let’s compute \(EA\).

The result of EA confirms the effect of adding 3 times the first row of \(A\) to the third row.

Now, let’s confirm this using a live Python environment right here in our presentation. We’ll use the numpy library, which is a staple in ECE for numerical computations. We define our matrix A and our elementary matrix E. Then, a simple np.dot(E, A) gives us the product. You can see how the third row of the resulting matrix accurately reflects the row operation. This hands-on computation reinforces the theorem.

Inverse Operations

For every elementary matrix \(E\), there’s an inverse elementary row operation that transforms \(E\) back to the identity matrix \(I\).

Row Operation on \(I\) That Produces \(E\)

• Multiply row \(i\) by \(c \neq 0\)
• Interchange rows \(i\) and \(j\)
• Add \(c\) times row \(i\) to row \(j\)

Row Operation on \(E\) That Reproduces \(I\)

• Multiply row \(i\) by \(1/c\)
• Interchange rows \(i\) and \(j\)
• Add \(-c\) times row \(i\) to row \(j\)

We discussed this briefly earlier: every elementary row operation has an inverse. This table summarizes those inverse operations. For example, if you scaled a row by \(c\), you can undo it by scaling it by \(1/c\). If you swapped two rows, swapping them again undoes the operation. And if you added \(c\) times one row to another, you undo it by adding \(-c\) times that same row. This reversibility leads us to an important theorem about elementary matrices themselves.

Theorem 1.5.2: Invertibility of Elementary Matrices

Every elementary matrix is invertible, and its inverse is also an elementary matrix.

This theorem is a building block for many results that follow.

This theorem is quite intuitive given what we just saw. Since every elementary row operation is reversible by another elementary row operation, and elementary matrices represent these operations, it logically follows that elementary matrices must be invertible. And furthermore, their inverse is also an elementary matrix. This is not just a theoretical curiosity; it’s a critical property that enables us to express any invertible matrix as a product of elementary matrices, which is a powerful concept in areas like digital signal processing and control system design.

Theorem 1.5.3: Equivalent Statements

If \(A\) is an \(n \times n\) matrix, then the following statements are equivalent (all true or all false):

1. \(A\) is invertible.
2. \(A\mathbf{x} = \mathbf{0}\) has only the trivial solution (\(\mathbf{x}=\mathbf{0}\)).
3. The reduced row echelon form (RREF) of \(A\) is \(I_n\).
4. \(A\) is expressible as a product of elementary matrices.

This theorem connects seemingly diverse ideas in linear algebra!

Now we come to one of the most significant theorems in introductory linear algebra: the Equivalent Statements Theorem. This theorem beautifully ties together concepts we’ve already learned and new ones like elementary matrices. It tells us that these four conditions are inextricably linked. If one is true, all are true. If one is false, all are false. This isn’t just theory; it has practical implications in ECE. For example, knowing that “A is invertible” is equivalent to “Ax=0 has only the trivial solution” tells us that a system of equations describing a circuit has a unique solution if and only if its coefficient matrix is invertible.

A Method for Inverting Matrices

Inversion Algorithm:

To find the inverse of an invertible matrix \(A\):

1. Form the augmented matrix \([A \mid I_n]\).
2. Perform a sequence of elementary row operations to reduce \(A\) to the identity matrix \(I_n\).
3. As you perform these operations on \(A\), simultaneously apply them to \(I_n\).
4. If \(A\) reduces to \(I_n\), the right side of the augmented matrix will be \(A^{-1}\). The final matrix will have the form \([I_n \mid A^{-1}]\).

This method leverages the fact that the same sequence of operations that transforms \(A\) to \(I_n\) will transform \(I_n\) to \(A^{-1}\).

This algorithm directly comes from the equivalence theorem and the idea of elementary matrices. If A is invertible, we know its RREF is the identity matrix. Each step of row reduction corresponds to multiplying by an elementary matrix. So, if \(E_k \dots E_1 A = I_n\), then multiplying by \(A^{-1}\) on the right, we get \(E_k \dots E_1 = A^{-1}\). This means the sequence of elementary matrices that transform A to I, when applied to I, will transform I to A inverse. This is the foundation of the Gauss-Jordan method for finding an inverse, a very practical algorithm in many engineering computations.

Example 4: Using Row Operations to Find \(A^{-1}\)

Find the inverse of \[ A = \left[ \begin{array}{lll}1 & 2 & 3 \\ 2 & 5 & 3 \\ 1 & 0 & 8 \end{array} \right] \]

We start with the augmented matrix \([A \mid I]\):

\[ \left[ \begin{array}{r r r | r r r}{1}&{2}&{3} & {1}&{0}&{0}\\ {2}&{5}&{3} & {0}&{1}&{0}\\ {1}&{0}&{8} & {0}&{0}&{1}\end{array} \right] \] Apply row operations: 1. \(R_2 \leftarrow R_2 - 2R_1\) 2. \(R_3 \leftarrow R_3 - R_1\)

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

Let’s walk through an example. We want to find the inverse of matrix A. We set up the augmented matrix by placing A on the left and the identity matrix on the right. Our goal is to transform the left side into the identity matrix using elementary row operations, and whatever we do to the left, we do to the right. The first step for Gauss-Jordan is to get zeros below the leading 1 in the first column. We perform R2 - 2R1 and R3 - R1. Observe how the operations are applied to both sides of the partition.

Example 4: Using Row Operations to Find \(A^{-1}\) (Cont.)

From previous step: \[ \left[ \begin{array}{r r r | r r r}{1}&{2}&{3} & {1}&{0}&{0}\\ {0}&{1}&{-3} & {-2}&{1}&{0}\\ {0}&{-2}&{5} & {-1}&{0}&{1}\end{array} \right] \] Apply row operations: 3. \(R_3 \leftarrow R_3 + 2R_2\)

\[ \left[ \begin{array}{r r r | r r r}{1}&{2}&{3} & {1}&{0}&{0}\\ {0}&{1}&{-3} & {-2}&{1}&{0}\\ {0}&{0}&{-1} & {-5}&{2}&{1}\end{array} \right] \] 4. \(R_3 \leftarrow -1 \cdot R_3\)

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

Continuing the process, we want to clear the entry below the leading 1 in the second column. So we perform R3 + 2R2. This gives us a 0 in the (3,2) position. Finally, to get the identity matrix on the left, we need a 1 in the (3,3) position. We achieve this by multiplying R3 by -1. Now, we have successfully created an upper triangular form, moving towards full Gauss-Jordan.

Example 4: Using Row Operations to Find \(A^{-1}\) (Cont.)

From previous step: \[ \left[ \begin{array}{r r r | r r r}{1}&{2}&{3} & {1}&{0}&{0}\\ {0}&{1}&{-3} & {-2}&{1}&{0}\\ {0}&{0}&{1} & {5}&{-2}&{-1}\end{array} \right] \] Apply row operations: 5. \(R_2 \leftarrow R_2 + 3R_3\) 6. \(R_1 \leftarrow R_1 - 3R_3\)

\[ \left[ \begin{array}{r r r | r r r}{1}&{2}&{0} & {-14}&{6}&{3}\\ {0}&{1}&{0} & {13}&{-5}&{-3}\\ {0}&{0}&{1} & {5}&{-2}&{-1}\end{array} \right] \] 7. \(R_1 \leftarrow R_1 - 2R_2\)

\[ \left[ \begin{array}{r r r | r r r}{1}&{0}&{0} & {-40}&{16}&{9}\\ {0}&{1}&{0} & {13}&{-5}&{-3}\\ {0}&{0}&{1} & {5}&{-2}&{-1}\end{array} \right] \]

Thus, the inverse is: \[ A^{-1} = \left[ \begin{array}{rrr} - 40 & 16 & 9 \\ 13 & -5 & -3 \\ 5 & -2 & -1 \end{array} \right] \]

Now we move to the “reverse” part of Gauss-Jordan, clearing elements above the leading 1s. First, we make the elements above the leading 1 in the third column zero. We do R2 + 3R3 and R1 - 3R3. This gives us zeros in the (1,3) and (2,3) positions. Finally, we clear the element above the leading 1 in the second column by performing R1 - 2R2. Successfully, we have reduced the left side to the identity matrix. The matrix on the right is now transformed into A inverse. This systematic approach is extremely reliable for finding matrix inverses.

Example 4: Python Verification

Let’s verify the inverse using numpy.linalg.inv.

The computed inverse matches our manual calculation, and \(A A^{-1} \approx I\).

To double-check our manual calculations, we can use numpy.linalg.inv, which is a highly optimized function for calculating matrix inverses. As you can see, the result from numpy matches our step-by-step example. We can also perform a quick check by multiplying the original matrix by its inverse, which, if correct, should yield the identity matrix. This is a common practice in engineering to verify calculations.

Example 5: Showing That a Matrix Is Not Invertible

Consider the matrix: \[ A = \left[ \begin{array}{rrr}1 & 6 & 4 \\ 2 & 4 & -1 \\ -1 & 2 & 5 \end{array} \right] \] Start with \([A \mid I]\) and apply row operations:

\[ \quad \left[ \begin{array}{r r r | r r r}{1} & {6} & {4} & {1} & {0} & {0}\\ {2} & {4} & {-1} & {0} & {1} & {0}\\ {-1} & {2} & {5} & {0} & {0} & {1} \end{array} \right] \] 1. \(R_2 \leftarrow R_2 - 2R_1\) 2. \(R_3 \leftarrow R_3 + R_1\)

\[ \left[ \begin{array}{r r r | r r r}{1} & {6} & {4} & {1} & {0} & {0}\\ {0} & {-8} & {-9} & {-2} & {1} & {0}\\ {0} & {8} & {9} & {1} & {0} & {1} \end{array} \right] \] 3. \(R_3 \leftarrow R_3 + R_2\)

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

Since we obtained a row of zeros on the left side, \(A\) is not invertible.

What if a matrix isn’t invertible? How does this algorithm tell us? Let’s take matrix A here. We’ll start the inversion process the same way. After the first set of row operations to clear the first column, we get to the second matrix. Now, when we try to clear the elements below the second pivot, specifically the (3,2) element, by adding R2 to R3, we find something crucial: the entire third row of the left part of the augmented matrix becomes zero. According to Theorem 1.5.3 part (c), if the reduced row echelon form of \(A\) is not \(I_n\), then \(A\) is not invertible. A row of zeros means we cannot reduce it to the identity matrix, hence \(A\) is singular, or non-invertible.

Example 5: Python Check for Non-Invertibility

What happens when numpy.linalg.inv tries to invert a singular matrix?

numpy correctly identifies the matrix as singular, consistent with our manual process.

Let’s see how numpy handles this. We use a try-except block because we expect an error. When np.linalg.inv is called on a singular matrix, it raises a LinAlgError, specifically indicating the matrix is singular. This confirms our manual observation: the appearance of a row of zeros on the left side during the inversion process is the clear signal that the matrix is not invertible. This concept is critical in ECE. For example, if a system matrix in circuit analysis turns out to be singular, it implies that the circuit equations do not have a unique solution, perhaps indicating a design flaw or a dependent set of equations.

Example 6: Analyzing Homogeneous Systems

Use Theorem 1.5.3 to determine whether the given homogeneous systems have nontrivial solutions.

System (a): \[ \begin{array}{r l} & {x_{1} + 2x_{2} + 3x_{3} = 0}\\ & {2x_{1} + 5x_{2} + 3x_{3} = 0}\\ & {x_{1} + 0x_{2} + 8x_{3} = 0} \end{array} \] Coefficient matrix: \(A = \left[ \begin{array}{lll}1 & 2 & 3 \\ 2 & 5 & 3 \\ 1 & 0 & 8 \end{array} \right]\) (from Example 4)

Example 6: Analyzing Homogeneous Systems

System (b): \[ \begin{array}{r l} & {x_{1} + 6x_{2} + 4x_{3} = 0}\\ & {2x_{1} + 4x_{2} - x_{3} = 0}\\ & {-x_{1} + 2x_{2} + 5x_{3} = 0} \end{array} \] Coefficient matrix: \(A = \left[ \begin{array}{rrr}1 & 6 & 4 \\ 2 & 4 & -1 \\ -1 & 2 & 5 \end{array} \right]\) (from Example 5)

Solution: From parts (a) and (b) of Theorem 1.5.3: a homogeneous linear system \(A\mathbf{x}=\mathbf{0}\) has only the trivial solution if and only if its coefficient matrix \(A\) is invertible.

• System (a)’s coefficient matrix (Example 4) is invertible. Thus, system (a) has only the trivial solution.
• System (b)’s coefficient matrix (Example 5) is NOT invertible. Thus, system (b) has nontrivial solutions.

This example directly shows the power of Theorem 1.5.3. We don’t even need to solve the systems explicitly. We can simply look at the invertibility of their coefficient matrices. For system (a), its coefficient matrix is the same one we successfully inverted in Example 4. Since it’s invertible, Theorem 1.5.3(a) implies Theorem 1.5.3(b) - the system \(A\mathbf{x}=\mathbf{0}\) has only the trivial solution. For system (b), its coefficient matrix is the singular matrix from Example 5. Since it’s not invertible, Theorem 1.5.3(a) is false, which means Theorem 1.5.3(b) is also false. Therefore, \(A\mathbf{x}=\mathbf{0}\) for system (b) must have non-trivial solutions. This is a very efficient way to determine the nature of solutions for homogeneous systems, which often arise in finding null spaces of linear transformations or analyzing stable states in dynamic systems in ECE.

ECE Applications & Summary

Key Concepts for ECE:

• System Analysis: Inverting matrices is crucial for solving systems of linear equations that model electrical circuits, control systems, and communication networks.
• Transformations: Elementary matrices represent fundamental transformations that can be applied to data (e.g., in signal processing or computer graphics).
• Invertibility: Determines if a unique solution exists for a given engineering problem (e.g., unique current/voltage in a circuit, unique control input for a desired output).

ECE Applications & Summary

Today We Covered:

• Elementary Row Operations and their matrix representation.
• The definition and invertibility of Elementary Matrices.
• The fundamental Equivalence Theorem linking invertibility, homogeneous solutions, RREF, and elementary matrices.
• A practical algorithm for finding \(A^{-1}\) using row operations.
• How to identify non-invertible matrices during the inversion process.

Let’s briefly tie back the theoretical concepts to practical ECE applications. The ability to solve systems of equations by inverting matrices is fundamental in circuit analysis to find unknown currents and voltages. In control systems, matrix inverses are used in state-space representations to design controllers. In signal processing, transformations often involve matrix multiplications. The concept of invertibility itself is critical: it tells us if a unique solution exists for a system of equations. For example, if a circuit’s matrix is singular, it might imply a redundant or ill-defined circuit.

To summarize, today we first revisited elementary row operations and introduced elementary matrices as their matrix multiplication equivalents. We proved that elementary matrices are always invertible. Then, we explored the powerful Equivalence Theorem, which unifies several core linear algebra concepts, providing deep insights into matrix properties. Finally, we learned and practiced a systematic algorithm to find matrix inverses and how to recognize when a matrix is not invertible. This forms a robust foundation for more advanced topics in matrices and linear transformations.