Chapter 6: Linear Systems Theory
Haiyue
17min
Chapter 6: Linear Systems Theory
Learning Objectives
- Understand the geometric meaning of linear systems
- Master the principles and steps of Gaussian elimination
- Understand row echelon form and reduced row echelon form
- Master the structure of solutions for homogeneous and non-homogeneous systems
- Understand the concept of solution space
Basic Concepts of Linear Systems
General Form of Linear Systems
A linear system consists of several linear equations:
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \end{cases}$$ **Matrix Form:** $$A\mathbf{x} = \mathbf{b}$$ Where: - $A$ is the $m \times n$ coefficient matrix - $\mathbf{x}$ is the $n \times 1$ unknown vector - $\mathbf{b}$ is the $m \times 1$ constant vector ```python import numpy as np import matplotlib.pyplot as plt from scipy.linalg import solve # Example: Linear system # 2x + 3y = 7 # x - y = 1 A = np.array([[2, 3], [1, -1]]) b = np.array([7, 1]) print("Coefficient matrix A:") print(A) print("\nConstant vector b:") print(b) # Solve the linear system solution = solve(A, b) print(f"\nSolution: x = {solution[0]:.2f}, y = {solution[1]:.2f}") # Verify the solution verification = A @ solution print(f"Verification: A @ x = {verification}") print(f"Original constant vector b = {b}") ``` ### Classification of Solutions Linear systems can have three types of solutions: 1. **Unique solution**: The system has exactly one solution 2. **Infinitely many solutions**: The system has infinitely many solutions 3. **No solution**: The system is inconsistent ::: note Solution Existence Criteria - **Has solution**: If and only if $\text{rank}(A) = \text{rank}([A|b])$ - **Unique solution**: When $\text{rank}(A) = \text{rank}([A|b]) = n$ ($n$ is the number of unknowns) - **Infinitely many solutions**: When $\text{rank}(A) = \text{rank}([A|b]) < n$ ::: ## Geometric Interpretation ### Two-Dimensional Case In the two-dimensional plane, each linear equation represents a line: ```python # Geometric interpretation visualization fig, axes = plt.subplots(1, 3, figsize=(15, 5)) # Case 1: Unique solution (two lines intersect) x = np.linspace(-1, 5, 100) y1 = (7 - 2*x) / 3 # 2x + 3y = 7 y2 = x - 1 # x - y = 1 axes[0].plot(x, y1, 'b-', label='2x + 3y = 7') axes[0].plot(x, y2, 'r-', label='x - y = 1') axes[0].plot(2.2, 0.2, 'go', markersize=8, label='Intersection (2.2, 0.2)') axes[0].grid(True, alpha=0.3) axes[0].legend() axes[0].set_title('Unique Solution: Two Lines Intersect') axes[0].set_xlim(-1, 5) axes[0].set_ylim(-2, 3) # Case 2: Infinitely many solutions (two lines coincide) y3 = (6 - 2*x) / 3 # 2x + 3y = 6 y4 = (6 - 2*x) / 3 # 4x + 6y = 12 (equivalent equation) axes[1].plot(x, y3, 'b-', linewidth=3, label='2x + 3y = 6') axes[1].plot(x, y4, 'r--', linewidth=2, label='4x + 6y = 12') axes[1].grid(True, alpha=0.3) axes[1].legend() axes[1].set_title('Infinitely Many Solutions: Lines Coincide') axes[1].set_xlim(-1, 5) axes[1].set_ylim(-1, 3) # Case 3: No solution (two lines are parallel) y5 = (7 - 2*x) / 3 # 2x + 3y = 7 y6 = (1 - 2*x) / 3 # 2x + 3y = 1 axes[2].plot(x, y5, 'b-', label='2x + 3y = 7') axes[2].plot(x, y6, 'r-', label='2x + 3y = 1') axes[2].grid(True, alpha=0.3) axes[2].legend() axes[2].set_title('No Solution: Lines Are Parallel') axes[2].set_xlim(-1, 5) axes[2].set_ylim(-2, 3) plt.tight_layout() plt.show() ``` ### Three-Dimensional Case In three-dimensional space, each linear equation represents a plane: ```python # 3D visualization example from mpl_toolkits.mplot3d import Axes3D fig = plt.figure(figsize=(12, 4)) # Intersection of three planes ax1 = fig.add_subplot(131, projection='3d') # Create grid x = np.linspace(-2, 2, 20) y = np.linspace(-2, 2, 20) X, Y = np.meshgrid(x, y) # Three planes: x + y + z = 1, x - y + z = 0, 2x + y - z = 1 Z1 = 1 - X - Y # x + y + z = 1 Z2 = X - Y # x - y + z = 0 Z3 = 2*X + Y - 1 # 2x + y - z = 1 ax1.plot_surface(X, Y, Z1, alpha=0.3, color='blue', label='Plane 1') ax1.plot_surface(X, Y, Z2, alpha=0.3, color='red', label='Plane 2') ax1.plot_surface(X, Y, Z3, alpha=0.3, color='green', label='Plane 3') # Compute intersection point A_3d = np.array([[1, 1, 1], [1, -1, 1], [2, 1, -1]]) b_3d = np.array([1, 0, 1]) solution_3d = solve(A_3d, b_3d) ax1.scatter(*solution_3d, color='black', s=100, label='Intersection Point') ax1.set_title('Three Planes Intersect at a Point') ax1.set_xlabel('X') ax1.set_ylabel('Y') ax1.set_zlabel('Z') plt.show() ``` ## Gaussian Elimination Gaussian elimination is the fundamental method for solving linear systems, transforming the coefficient matrix into row echelon form through row operations. ### Elementary Row Operations 1. **Row exchange**: $R_i \leftrightarrow R_j$ 2. **Row scaling**: $R_i \leftarrow kR_i$ ($k \neq 0$) 3. **Row addition**: $R_i \leftarrow R_i + kR_j$ ```python def gaussian_elimination(A, b): """ Gaussian elimination to solve linear system Ax = b """ n = len(b) # Construct augmented matrix augmented = np.column_stack([A.astype(float), b.astype(float)]) print("Initial augmented matrix:") print(augmented) print() # Forward elimination for i in range(n): # Find pivot max_row = i for k in range(i+1, n): if abs(augmented[k, i]) > abs(augmented[max_row, i]): max_row = k # Swap rows if max_row != i: augmented[i], augmented[max_row] = augmented[max_row].copy(), augmented[i].copy() print(f"Swap row {i+1} and row {max_row+1}:") print(augmented) print() # Elimination for k in range(i+1, n): if augmented[i, i] != 0: factor = augmented[k, i] / augmented[i, i] augmented[k] = augmented[k] - factor * augmented[i] print(f"Row {k+1} <- Row {k+1} - {factor:.3f} * Row {i+1}:") print(augmented) print() print("Row echelon form matrix:") print(augmented) print() # Back substitution x = np.zeros(n) for i in range(n-1, -1, -1): x[i] = augmented[i, n] for j in range(i+1, n): x[i] -= augmented[i, j] * x[j] x[i] /= augmented[i, i] return x # Example A_example = np.array([[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]) b_example = np.array([8, -11, -3]) print("Solving the system:") print("2x + y - z = 8") print("-3x - y + 2z = -11") print("-2x + y + 2z = -3") print() solution = gaussian_elimination(A_example, b_example) print(f"Solution: x = {solution}") ``` ### Row Echelon Form and Reduced Row Echelon Form **Row Echelon Form (REF)** characteristics: 1. Zero rows (if any) are at the bottom of the matrix 2. The leading entry (pivot) of each non-zero row is to the right of the pivot in the row above 3. All entries below a pivot are zero **Reduced Row Echelon Form (RREF)** characteristics: 1. Satisfies all conditions of row echelon form 2. Each pivot is 1 3. All entries above and below each pivot are zero ```python def rref(matrix): """ Transform matrix to reduced row echelon form """ A = matrix.astype(float).copy() rows, cols = A.shape current_row = 0 for col in range(cols): # Find pivot pivot_row = current_row while pivot_row < rows and A[pivot_row, col] == 0: pivot_row += 1 if pivot_row == rows: continue # Swap rows if pivot_row != current_row: A[current_row], A[pivot_row] = A[pivot_row].copy(), A[current_row].copy() # Scale pivot to 1 A[current_row] = A[current_row] / A[current_row, col] # Eliminate other elements in this column for row in range(rows): if row != current_row and A[row, col] != 0: A[row] = A[row] - A[row, col] * A[current_row] current_row += 1 if current_row == rows: break return A # Example matrix_example = np.array([[1, 2, -1, 3], [2, 4, 1, 7], [1, 2, 2, 6]]) print("Original matrix:") print(matrix_example) print("\nReduced row echelon form:") rref_matrix = rref(matrix_example) print(rref_matrix) ``` ## Homogeneous Systems ### Definition of Homogeneous Systems The form of a homogeneous linear system is: $$A\mathbf{x} = \mathbf{0}$$ **Important properties:** 1. Homogeneous systems always have a solution (at least the zero solution) 2. If $\mathbf{x}_1$ and $\mathbf{x}_2$ are solutions, then $c_1\mathbf{x}_1 + c_2\mathbf{x}_2$ is also a solution 3. The solution set forms a vector space (null space or kernel) ```python def homogeneous_solution(A): """ Find the general solution of homogeneous system Ax = 0 """ print("Homogeneous system Ax = 0") print("Coefficient matrix A:") print(A) # Transform to reduced row echelon form rref_A = rref(A) print("\nReduced row echelon form:") print(rref_A) m, n = A.shape rank_A = np.linalg.matrix_rank(A) print(f"\nRank of matrix: {rank_A}") print(f"Number of free variables: {n - rank_A}") if rank_A == n: print("Only zero solution") return np.zeros((n, 1)) else: print("Has non-zero solutions") # Simplified handling; actual applications need more complex algorithms to find basis return None # Example A_homogeneous = np.array([[1, 2, 3], [2, 4, 6], [1, 2, 3]]) homogeneous_solution(A_homogeneous) ``` ## Non-Homogeneous Systems ### Structure of Solutions Theorem For a non-homogeneous system $A\mathbf{x} = \mathbf{b}$: If the system has a solution, the general solution is: $$\mathbf{x} = \mathbf{x}_p + \mathbf{x}_h$$ Where: - $\mathbf{x}_p$ is a particular solution (any solution of the non-homogeneous system) - $\mathbf{x}_h$ is the general solution of the corresponding homogeneous system $A\mathbf{x} = \mathbf{0}$ ```python def analyze_system(A, b): """ Analyze the solution behavior of a linear system """ m, n = A.shape # Compute rank of coefficient matrix rank_A = np.linalg.matrix_rank(A) # Compute rank of augmented matrix augmented = np.column_stack([A, b]) rank_Ab = np.linalg.matrix_rank(augmented) print(f"Coefficient matrix A shape: {A.shape}") print(f"rank(A) = {rank_A}") print(f"rank([A|b]) = {rank_Ab}") print(f"Number of unknowns: {n}") print() if rank_A != rank_Ab: print("System has no solution (inconsistent)") return None elif rank_A == rank_Ab == n: print("System has a unique solution") solution = solve(A, b) print(f"Solution: {solution}") return solution else: print(f"System has infinitely many solutions") print(f"Number of free variables: {n - rank_A}") return "Infinitely many solutions" # Test different cases print("Case 1: Unique solution") A1 = np.array([[1, 2], [3, 4]]) b1 = np.array([5, 6]) analyze_system(A1, b1) print("\n" + "="*50 + "\n") print("Case 2: No solution") A2 = np.array([[1, 2], [2, 4]]) b2 = np.array([3, 7]) analyze_system(A2, b2) print("\n" + "="*50 + "\n") print("Case 3: Infinitely many solutions") A3 = np.array([[1, 2], [2, 4]]) b3 = np.array([3, 6]) analyze_system(A3, b3) ``` ## Concept of Solution Space ### Null Space The null space of matrix $A$ is the solution set of the homogeneous system $A\mathbf{x} = \mathbf{0}$: $$\text{Null}(A) = \{\mathbf{x} \in \mathbb{R}^n : A\mathbf{x} = \mathbf{0}\}$$ **Properties:** - The null space is a subspace of $\mathbb{R}^n$ - $\dim(\text{Null}(A)) = n - \text{rank}(A)$ (Rank-Nullity Theorem) ```python def null_space_visualization(): """ Visualize the concept of null space """ # 2D case: null space is a line fig, axes = plt.subplots(1, 2, figsize=(12, 5)) # Case 1: rank = 1, null space is a line # Equation: x + 2y = 0 x = np.linspace(-3, 3, 100) y = -x / 2 axes[0].plot(x, y, 'b-', linewidth=2, label='x + 2y = 0') axes[0].arrow(0, 0, 2, -1, head_width=0.1, head_length=0.1, fc='red', ec='red') axes[0].arrow(0, 0, -2, 1, head_width=0.1, head_length=0.1, fc='red', ec='red') axes[0].grid(True, alpha=0.3) axes[0].set_aspect('equal') axes[0].legend() axes[0].set_title('Null Space: Line (1D Subspace)') axes[0].set_xlim(-3, 3) axes[0].set_ylim(-3, 3) # Case 2: rank = 2, null space is only the origin axes[1].plot(0, 0, 'ro', markersize=8, label='Null space: {0}') axes[1].grid(True, alpha=0.3) axes[1].set_aspect('equal') axes[1].legend() axes[1].set_title('Null Space: Origin (0D Subspace)') axes[1].set_xlim(-3, 3) axes[1].set_ylim(-3, 3) plt.tight_layout() plt.show() null_space_visualization() ``` ### Column Space The column space of matrix $A$ is the set of all linear combinations of $A$'s column vectors: $$\text{Col}(A) = \{\mathbf{b} \in \mathbb{R}^m : A\mathbf{x} = \mathbf{b} \text{ has a solution}\}$$ ```python def visualize_column_space(): """ Visualize column space """ fig = plt.figure(figsize=(10, 8)) ax = fig.add_subplot(111, projection='3d') # Two column vectors of matrix v1 = np.array([1, 0, 1]) v2 = np.array([0, 1, 1]) # Column space is the plane spanned by these two vectors u = np.linspace(-2, 2, 20) v = np.linspace(-2, 2, 20) U, V = np.meshgrid(u, v) # Points on the plane X = U * v1[0] + V * v2[0] Y = U * v1[1] + V * v2[1] Z = U * v1[2] + V * v2[2] ax.plot_surface(X, Y, Z, alpha=0.3, color='lightblue') # Draw basis vectors ax.quiver(0, 0, 0, v1[0], v1[1], v1[2], color='red', arrow_length_ratio=0.1, linewidth=3, label='v1') ax.quiver(0, 0, 0, v2[0], v2[1], v2[2], color='blue', arrow_length_ratio=0.1, linewidth=3, label='v2') ax.set_xlabel('X') ax.set_ylabel('Y') ax.set_zlabel('Z') ax.set_title('Column Space: Plane Spanned by Two Vectors') ax.legend() plt.show() visualize_column_space() ``` ## Algorithm Summary ```mermaid graph TD A[Linear System Ax = b] --> B{rank(A) = rank([A|b])?} B -->|No| C[No Solution] B -->|Yes| D{rank(A) = n?} D -->|Yes| E[Unique Solution] D -->|No| F[Infinitely Many Solutions] E --> G[Gaussian Elimination] F --> H[General Solution = Particular + Homogeneous] G --> I[Back Substitution] H --> J[RREF + Parametric Representation] ``` ## Practical Application Example ### Circuit Analysis ```python # Circuit network analysis example def circuit_analysis(): """ Circuit analysis using Kirchhoff's laws """ print("Circuit Analysis: Kirchhoff's Laws") print("Node voltage method to solve circuit currents") # Coefficient matrix of example circuit (based on Kirchhoff's current law) # 3 loops, 3 unknown currents A_circuit = np.array([[10, -5, 0], # Loop 1 [-5, 15, -2], # Loop 2 [ 0, -2, 7]]) # Loop 3 b_circuit = np.array([12, 0, -5]) # Voltage sources print("Coefficient matrix (resistance matrix):") print(A_circuit) print("\nVoltage vector:") print(b_circuit) currents = solve(A_circuit, b_circuit) print(f"\nBranch currents: {currents}") print(f"I1 = {currents[0]:.3f} A") print(f"I2 = {currents[1]:.3f} A") print(f"I3 = {currents[2]:.3f} A") circuit_analysis() ``` ## Chapter Summary | Concept | Definition | Important Properties | |------|------|----------| | Linear System | $A\mathbf{x} = \mathbf{b}$ | May have unique solution, infinitely many solutions, or no solution | | Gaussian Elimination | Row operations to simplify matrix | Transforms matrix to row echelon form | | Homogeneous System | $A\mathbf{x} = \mathbf{0}$ | Solution set forms a vector space | | Non-homogeneous System | $A\mathbf{x} = \mathbf{b}$ | General solution = Particular solution + Homogeneous solution | | Null Space | $\text{Null}(A)$ | $\dim = n - \text{rank}(A)$ | | Column Space | $\text{Col}(A)$ | Condition for system to have a solution | ::: warning Important Notes - Pay attention to the impact of rounding errors in numerical computation - Pivot selection is important for algorithm stability - The structure of solutions theory is a core content of linear algebra ::: Linear systems theory perfectly combines geometric intuition, algebraic operations, and theoretical analysis, laying a solid foundation for subsequent study of matrix theory and linear transformations.