Linear Algebra

1.6 More on Linear Systems and Invertible Matrices

Imron Rosyadi

Linear Algebra in ECE

1.6 More on Linear Systems and Invertible Matrices

Imron Rosyadi

Leveraging matrix inverses to efficiently solve linear systems and deepen our understanding of system properties.

Good morning everyone! Today, we’re building on our previous discussion about elementary matrices and invertibility. We’ll explore how the inverse of a matrix provides a direct formula for solving certain types of linear systems, and we’ll further expand our understanding of invertible matrices and their crucial role in system analysis within Electrical and Computer Engineering.

Number of Solutions of a Linear System

THEOREM 1.6.1 A system of linear equations has zero, one, or infinitely many solutions. There are no other possibilities.

Proof Idea: If \(A\mathbf{x} = \mathbf{b}\) has more than one solution (\(\mathbf{x}_1\) and \(\mathbf{x}_2\)), then their difference \(\mathbf{x}_0 = \mathbf{x}_1 - \mathbf{x}_2 \ne \mathbf{0}\) is a non-trivial solution to the associated homogeneous system \(A\mathbf{x} = \mathbf{0}\).

Then, for any scalar \(k\), \(\mathbf{x}_1 + k\mathbf{x}_0\) is also a solution to \(A\mathbf{x} = \mathbf{b}\). \[ A(\mathbf{x}_{1}+k\mathbf{x}_{0})=A\mathbf{x}_{1}+k(A\mathbf{x}_{0}) = \mathbf{b}+k\mathbf{0}=\mathbf{b} \] Since there are infinitely many choices for \(k\), there are infinitely many solutions.

Number of Solutions of a Linear System

Visualizing Solution Spaces

graph TD
    A[Linear System Ax=b] --> B{Number of Solutions?};
    B --> C{Zero};
    B --> D{One};
    B --> E{Infinitely Many};

This fundamental theorem applies to any linear system, regardless of its size or the properties of its coefficient matrix.

We’ve seen this concept intuitively in earlier sections by looking at lines and planes. Now, Theorem 1.6.1 formally proves that these are the only three outcomes for any linear system. The key insight in the proof is that if you have two distinct solutions, their difference forms a non-trivial solution to the homogeneous system. This non-trivial solution can then be scaled by any real number and added to one of the original solutions to generate an infinite number of new solutions. This has implications for understanding degrees of freedom in engineering problems, such as current flow in a network.

Solving Linear Systems by Matrix Inversion

THEOREM 1.6.2 If \(A\) is an invertible \(n \times n\) matrix, then for each \(n \times 1\) matrix \(\mathbf{b}\), the system of equations \(A\mathbf{x} = \mathbf{b}\) has exactly one solution, namely, \(\mathbf{x} = A^{-1}\mathbf{b}\).

Proof Idea:

1. Existence:

Verify that \(\mathbf{x} = A^{-1}\mathbf{b}\) is indeed a solution: \(A(A^{-1}\mathbf{b}) = (AA^{-1})\mathbf{b} = I\mathbf{b} = \mathbf{b}\).

2. Uniqueness:

Assume \(\mathbf{x}_0\) is any solution, so \(A\mathbf{x}_0 = \mathbf{b}\).

Multiply by \(A^{-1}\) from the left: \(A^{-1}(A\mathbf{x}_0) = A^{-1}\mathbf{b} \implies (A^{-1}A)\mathbf{x}_0 = A^{-1}\mathbf{b} \implies I\mathbf{x}_0 = A^{-1}\mathbf{b} \implies \mathbf{x}_0 = A^{-1}\mathbf{b}\).

This method provides a direct formula to find the solution.

Theorem 1.6.2 is incredibly important. It’s often the first “formula” students encounter for solving a system of linear equations beyond Gaussian elimination. In ECE, many problems, like solving for node voltages in a circuit using Kirchhoff’s laws or analyzing steady-state responses of control systems, boil down to \(A\mathbf{x}=\mathbf{b}\). If the system’s matrix \(A\) is invertible, we can directly compute the solution \(\mathbf{x}\) by finding \(A^{-1}\) and multiplying it by \(\mathbf{b}\). This is particularly useful in computer simulations and numerical analysis where matrix inversion libraries are readily available.

Example 1: Solution of a Linear System Using \(A^{-1}\)

Consider the system: \[ \begin{array}{r}{x_{1} + 2x_{2} + 3x_{3} = 5}\\ {2x_{1} + 5x_{2} + 3x_{3} = 3}\\ {x_{1}\qquad +8x_{3} = 17} \end{array} \] In matrix form \(A\mathbf{x} = \mathbf{b}\): \[ A = {\left[ \begin{array}{l l l}{1} & {2} & {3}\\ {2} & {5} & {3}\\ {1} & {0} & {8} \end{array} \right]},\quad \mathbf{x} = {\left[ \begin{array}{l}{x_{1}}\\ {x_{2}}\\ {x_{3}} \end{array} \right]},\quad \mathbf{b} = {\left[ \begin{array}{l}{5}\\ {3}\\ {17} \end{array} \right]} \] From Example 4 of the preceding section, we know \(A^{-1}\): \[ A^{-1} = \left[ \begin{array}{rrr} - 40 & 16 & 9 \\ 13 & -5 & -3 \\ 5 & -2 & -1 \end{array} \right] \] By Theorem 1.6.2, the solution is \(\mathbf{x} = A^{-1}\mathbf{b}\).

Let’s apply Theorem 1.6.2 to a concrete example. This is the same coefficient matrix \(A\) we used in Example 4 from the previous lecture, where we found its inverse. We have a new right-hand side vector \(\mathbf{b}\). Now, all we need to do is perform the matrix-vector multiplication \(A^{-1}\mathbf{b}\) to get the solution \(\mathbf{x}\). This direct computational approach bypasses the need for Gaussian elimination for each new \(\mathbf{b}\), provided \(A^{-1}\) is already known or easily computed.

Example 1: Python Calculation of Solution

Let’s compute \(\mathbf{x} = A^{-1}\mathbf{b}\) using numpy.

The solution is \(x_1 = 1, x_2 = -1, x_3 = 2\).

This method is efficient when \(A^{-1}\) is already known.

Here’s the calculation in Python. We define the inverse matrix \(A^{-1}\) and the vector \(\mathbf{b}\). Using np.dot for matrix-vector multiplication, we quickly find the solution vector \(\mathbf{x}\). As you can see, \(x_1 = 1, x_2 = -1, x_3 = 2\). This demonstrates the beauty and efficiency of using matrix inversion for solving linear systems, especially when you need to solve many systems with the same coefficient matrix but different right-hand sides, a common scenario in signal processing filters or circuit analysis configurations.

Linear Systems with a Common Coefficient Matrix

Often, we need to solve sequences of systems: \[ A\mathbf{x} = \mathbf{b}_1,\quad A\mathbf{x} = \mathbf{b}_2,\quad \ldots ,\quad A\mathbf{x} = \mathbf{b}_k \] all sharing the same square coefficient matrix \(A\).

If \(A\) is invertible, solutions are \(\mathbf{x}_j = A^{-1}\mathbf{b}_j\). This involves one inversion and \(k\) multiplications.

Efficient Approach (Gauss-Jordan combined): Form the partitioned matrix: \[ [A\mid \mathbf{b}_{1}\mid \mathbf{b}_{2}\mid \dots \mid \mathbf{b}_{k}] \] Reduce this entire matrix to reduced row echelon form. The solutions \(\mathbf{x}_j\) will appear in the columns corresponding to \(\mathbf{b}_j\) on the right side once \(A\) is reduced to \(I\).

This method works even if \(A\) is not invertible (you’d still see the consistency conditions and solutions, if any).

In engineering, it’s very common to encounter multiple linear systems that share the same underlying structure, meaning they have the same coefficient matrix \(A\), but different input or output vectors \(\mathbf{b}\). Think about analyzing a circuit under different input voltage conditions, or a control system responding to various disturbances. Instead of solving each system individually or inverting \(A\) once and then multiplying \(k\) times, we can use a highly efficient approach: augment the coefficient matrix with all the right-hand side vectors at once and perform a single Gauss-Jordan elimination. This simultaneously solves all systems, saving significant computational effort.

Example 2: Solving Two Linear Systems at Once

Solve the systems:

1. \(x_1+2x_2+3x_3=4\)
   \(2x_1+5x_2+3x_3=5\)
   \(x_1\qquad+8x_3=9\)

2. \(x_1+2x_2+3x_3=1\)
   \(2x_1+5x_2+3x_3=6\)
   \(x_1\qquad+8x_3=-6\)

Coefficient matrix is \(A = \left[ \begin{array}{lll}1 & 2 & 3 \\ 2 & 5 & 3 \\ 1 & 0 & 8 \end{array} \right]\) for both.

Example 2: Solving Two Linear Systems at Once

Augmented matrix \([A \mid \mathbf{b}_a \mid \mathbf{b}_b]\): \[ \left[ \begin{array}{lllll}1 & 2 & 3 & 4 & 1 \\ 2 & 5 & 3 & 5 & 6 \\ 1 & 0 & 8 & 9 & -6 \end{array} \right] \] Reducing this to reduced row echelon form yields: \[ \left[ \begin{array}{lllll}1 & 0 & 0 & 1 & 2 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & -1 \end{array} \right] \] Solution for (a):

\(x_1 = 1, x_2 = 0, x_3 = 1\).

Solution for (b):

\(x_1 = 2, x_2 = 1, x_3 = -1\).

Here, we have two systems with the same \(A\) matrix, which we already know is invertible from previous examples. We form the combined augmented matrix. After performing Gauss-Jordan elimination (the steps are omitted here for brevity, but you can verify them), the RREF directly gives us the solutions. The fourth column corresponds to the solution of system (a), and the fifth column to the solution of system (b). This illustrates how compact and efficient solving multiple systems simultaneously can be.

Example 2: Python Verification of Combined Solution

Let’s use numpy.linalg.solve to confirm the solutions.

The computed solutions match the results from the combined Gauss-Jordan reduction.

While the previous slide showed the manual Gauss-Jordan approach, numpy provides a convenient linalg.solve function, which is designed for solving \(A\mathbf{x}=\mathbf{b}\). It’s often more numerically stable and efficient than directly computing \(A^{-1}\) and then multiplying. Here, we confirm that the solutions found by the simultaneous reduction are indeed correct by solving each system individually using numpy. This confirms the power of our linear algebra tools.

Properties of Invertible Matrices

Conventionally, for a matrix \(B\) to be the inverse of \(A\), we need both \(AB=I\) and \(BA=I\).

THEOREM 1.6.3 Let \(A\) be a square matrix.

1. If \(B\) is a square matrix satisfying \(BA = I\), then \(B = A^{-1}\).
2. If \(B\) is a square matrix satisfying \(AB = I\), then \(B = A^{-1}\).

Significance: To show that \(B\) is the inverse of \(A\), you only need to verify one of the conditions (\(AB=I\) or \(BA=I\)). The other condition holds automatically for square matrices.

Proof Idea for (a):

Assume \(BA=I\). We need to show \(A\) is invertible. If \(A\) is invertible, then \((BA)A^{-1} = IA^{-1} \implies B(AA^{-1}) = A^{-1} \implies BI = A^{-1} \implies B=A^{-1}\).

To show \(A\) is invertible, we use Theorem 1.5.3: show \(A\mathbf{x}=\mathbf{0}\) has only the trivial solution. If \(A\mathbf{x}_0 = \mathbf{0}\), then \(B(A\mathbf{x}_0) = B\mathbf{0} \implies I\mathbf{x}_0 = \mathbf{0} \implies \mathbf{x}_0 = \mathbf{0}\). So \(A\) is invertible.

This theorem often simplifies theoretical work and proofs involving matrix inverses. You might wonder, given the definition of an inverse requires both \(AB=I\) and \(BA=I\), why do we need both? Theorem 1.6.3 states that for square matrices, if you find a matrix that satisfies one of these conditions, it automatically satisfies the other. This isn’t true for non-square matrices, but it’s a very helpful property for square matrices. The proof relies on connecting back to the equivalent statements theorem from the last lecture, particularly that if \(A\mathbf{x}=\mathbf{0}\) has only the trivial solution, then \(A\) is invertible.

THEOREM 1.6.4: Extended Equivalent Statements

If \(A\) is an \(n \times n\) matrix, then the following are equivalent:

1. \(A\) is invertible.
2. \(A\mathbf{x} = \mathbf{0}\) has only the trivial solution.
3. The reduced row echelon form of \(A\) is \(I_{n}\).
4. \(A\) is expressible as a product of elementary matrices.
5. \(A\mathbf{x} = \mathbf{b}\) is consistent for every \(n \times 1\) matrix \(\mathbf{b}\).
6. \(A\mathbf{x} = \mathbf{b}\) has exactly one solution for every \(n \times 1\) matrix \(\mathbf{b}\).

We’re expanding our powerful Equivalence Theorem! We previously established the equivalence of (a), (b), (c), and (d). Now, we add two more critical conditions that relate to the solvability of general linear systems. (e) means that for an invertible matrix A, no matter what right-hand side vector \(\mathbf{b}\) you put in, a solution always exists. (f) takes it a step further: not only does a solution exist, but that solution is unique. These new equivalences are intuitively linked to parts (a) and (b) of the theorem. In ECE, this means if your system is ‘well-behaved’ (matrix A is invertible), you always get a predictive, unique output for any given input.

Invertibility of Product Matrices

THEOREM 1.6.5 Let \(A\) and \(B\) be square matrices of the same size. If \(AB\) is invertible, then \(A\) and \(B\) must also be invertible.

ECE Relevance: This theorem is important when considering cascading systems or transformations. If you have two operations represented by matrices \(A\) and \(B\) performing sequentially (\(AB\)), and their combined effect is reversible (invertible), then each individual operation (\(A\) and \(B\)) must also be reversible. This applies to signal processing chains, control system components, or multi-stage filters.

Proof Idea for B invertible: Assume \(\mathbf{x}_0\) is a solution to \(B\mathbf{x}=\mathbf{0}\). Then \((AB)\mathbf{x}_0 = A(B\mathbf{x}_0) = A\mathbf{0} = \mathbf{0}\). Since \(AB\) is invertible, by Theorem 1.6.4 (a) \(\Leftrightarrow\) (b), the system \((AB)\mathbf{x}=\mathbf{0}\) has only the trivial solution. Thus \(\mathbf{x}_0 = \mathbf{0}\). Therefore, \(B\) is invertible. Once \(B\) is invertible, then \(A = (AB)B^{-1}\), which is a product of invertible matrices, therefore \(A\) is also invertible.

This theorem is quite intuitive in a practical sense. If you combine two devices or processes in series, and the overall system is reversible (meaning you can undo its effect), then each individual device or process must also be reversible. If either \(A\) or \(B\) were singular (not invertible), it would “destroy” information and make the combined product \(AB\) singular as well, preventing it from being invertible. This theorem assures us that for a reversible cascade, all components must also be reversible.

The Fundamental Problem: Consistency Conditions

Problem: Let \(A\) be a fixed \(m \times n\) matrix. Find all \(m \times 1\) matrices \(\mathbf{b}\) such that the system of equations \(A\mathbf{x} = \mathbf{b}\) is consistent.

• Case 1: \(A\) is invertible (\(n \times n\) square matrix)
  • By Theorem 1.6.2 and 1.6.4, \(A\mathbf{x}=\mathbf{b}\) has a unique solution \(\mathbf{x} = A^{-1}\mathbf{b}\) for every \(\mathbf{b}\). So, no conditions on \(\mathbf{b}\).
• Case 2: \(A\) is not square, or \(A\) is square but not invertible.
  • Theorem 1.6.2 does not apply.
  • \(\mathbf{b}\) must usually satisfy certain conditions for \(A\mathbf{x}=\mathbf{b}\) to be consistent.
  • We use row reduction on \([A \mid \mathbf{b}]\) to identify these conditions.

This “fundamental problem” drives many investigations in linear algebra and its applications. It asks: for what inputs \(\mathbf{b}\) will a given system \(A\mathbf{x}=\mathbf{b}\) actually produce a solution? If \(A\) is an invertible square matrix, the answer is simple: any \(\mathbf{b}\) will work, and the solution is unique. This is ideal; it means your system can process any valid input. However, if \(A\) is not square (e.g., more equations than unknowns, or vice versa) or is a singular square matrix, then not all vectors \(\mathbf{b}\) will result in a consistent system. We saw an example of this in the previous lecture with singular matrices leading to inconsistent systems visually. In these cases, we must find specific conditions on \(\mathbf{b}\). This often tells engineers about the range or subspace of possible outputs from their system.

Example 3: Determining Consistency by Elimination

What conditions must \(b_1, b_2, b_3\) satisfy for the system to be consistent? \[ \begin{array}{r}x_{1} + x_{2} + 2x_{3} = b_{1} \\ x_{1} + x_{3} = b_{2} \\ 2x_{1} + x_{2} + 3x_{3} = b_{3} \end{array} \] Augmented matrix \([A \mid \mathbf{b}]\): \[ \left[ \begin{array}{llll}1 & 1 & 2 & b_{1} \\ 1 & 0 & 1 & b_{2} \\ 2 & 1 & 3 & b_{3} \end{array} \right] \] Row reducing to row echelon form: \[ \left[ \begin{array}{rrrr}1 & 1 & 2 & b_{1} \\ 0 & -1 & -1 & b_{2} - b_{1} \\ 0 & -1 & -1 & b_{3} - 2b_{1} \end{array} \right] \quad \xrightarrow{R_2 \leftarrow -R_2} \quad \left[ \begin{array}{rrrr}1 & 1 & 2 & b_{1} \\ 0 & 1 & 1 & b_{1} - b_{2} \\ 0 & -1 & -1 & b_{3} - 2b_{1} \end{array} \right] \] \[ \xrightarrow{R_3 \leftarrow R_3 + R_2} \quad \left[ \begin{array}{rrrr}1 & 1 & 2 & b_{1} \\ 0 & 1 & 1 & b_{1} - b_{2} \\ 0 & 0 & 0 & b_{3} - b_{2} - b_{1} \end{array} \right] \] For consistency, the last row implies: \(b_3 - b_2 - b_1 = 0 \implies b_3 = b_1 + b_2\). So, \(\mathbf{b}\) must be of the form \(\left[ \begin{array}{c}b_{1} \\ b_{2} \\ b_{1} + b_{2} \end{array} \right]\).

Let’s see an example of Case 2 where \(A\) is singular or not square. Here, as we reduce the augmented matrix, we notice that the left side develops a row of zeros. For the system to be consistent, the corresponding entry on the right-hand side of that zero row must also be zero. This gives us a condition on \(b_1, b_2, b_3\). In this case, \(b_3\) must be the sum of \(b_1\) and \(b_2\). This means not all \(\mathbf{b}\) vectors will lead to a solution for this particular system. In an ECE context, this might indicate that your system cannot produce arbitrary outputs, but rather its outputs are constrained to a specific subspace.

Example 4: Determining Consistency by Elimination (System from Ex. 1)

What conditions must \(b_1, b_2, b_3\) satisfy for the system to be consistent? \[ \begin{array}{r}x_{1} + 2x_{2} + 3x_{3} = b_{1} \\ 2x_{1} + 5x_{2} + 3x_{3} = b_{2} \\ x_{1} + 8x_{3} = b_{3} \end{array} \] (This is \(A\mathbf{x}=\mathbf{b}\) where \(A\) is the invertible matrix from Example 1).

Augmented matrix \([A \mid \mathbf{b}]\): \[ \left[ \begin{array}{llll}1 & 2 & 3 & b_1\\ 2 & 5 & 3 & b_2\\ 1 & 0 & 8 & b_3 \end{array} \right] \] Reducing this to reduced row echelon form yields (as seen when finding \(A^{-1}\)): \[ \begin{array}{r}\left[ \begin{array}{cccc}1 & 0 & 0 & -40b_1 + 16b_2 + 9b_3\\ 0 & 1 & 0 & 13b_1 - 5b_2 - 3b_3\\ 0 & 0 & 1 & 5b_1 - 2b_2 - b_3 \end{array} \right] \end{array} \] Result: There are no restrictions on \(b_1, b_2, b_3\). The system has a unique solution for all values of \(b_1, b_2, b_3\). This confirms Theorem 1.6.4 (e) and (f) for invertible matrices.

Let’s reconsider the matrix from Example 1, which we know is invertible. If we augment it with a generic \(\mathbf{b}\) vector and perform Gauss-Jordan elimination, we’ll see that the left side reduces to the identity matrix. This means there are no rows of zeros on the left, and therefore no consistency conditions on the \(b_i\) values. The right side simply provides the unique solution terms in terms of \(b_1, b_2, b_3\). This directly demonstrates Theorem 1.6.4 parts (e) and (f) in action: if \(A\) is invertible, then \(A\mathbf{x}=\mathbf{b}\) is consistent for every \(\mathbf{b}\) and has exactly one solution. This is the ideal behavior for many ECE applications.

ECE Applications & Summary

Key Concepts for ECE:

• Existence and Uniqueness of Solutions: Critical for ensuring that models of circuits, control systems, or communication links have predictable and solvable outcomes.
  • System behaves consistently.
  • Output is uniquely determined by input.
• Efficient System Solving:
  • Using \(A^{-1}\) for direct \(\mathbf{x} = A^{-1}\mathbf{b}\) when \(A\) is invertible.
  • Solving multiple systems simultaneously via augmented matrices. Reduces computation in large-scale simulations.
• System Properties: Invertibility of component matrices and their product defines the overall reversibility and predictability of complex engineering systems.

ECE Applications & Summary

Today We Covered:

• The fundamental theorem that linear systems have 0, 1, or ∞ solutions.
• Solving \(A\mathbf{x}=\mathbf{b}\) using \(A^{-1}\) for invertible \(A\).
• Simultaneous solution of multiple linear systems with a common coefficient matrix.
• Properties of invertible matrices, including the extended Equivalence Theorem.
• How to determine consistency conditions for \(A\mathbf{x}=\mathbf{b}\) by elimination.

To conclude, today’s lecture reinforced the practicality of matrix inverses and the theoretical backbone of linear system solutions. We formally proved that linear systems can only have zero, one, or infinitely many solutions. Crucially, for invertible square matrices, we learned how to directly solve \(A\mathbf{x}=\mathbf{b}\) using \(A^{-1}\), and how to efficiently tackle multiple systems at once. We also expanded our understanding of invertible matrices through new equivalences and the product invertibility theorem. Engineers must understand these concepts to ensure their models yield consistent and unique solutions.