Linear Algebra and Analytic Geometry · 120 h · Topic 3 of 9

Systems of linear equations

Solving a three-mesh circuit, fitting a calibration curve or simulating an entire network are the same problem: A·x = b. Only the size changes.

Gauss-Jordan Rouché-Frobenius Homogeneous systems Pivoting Mesh analysis

01Where linear systems come from

Almost every engineering problem ends up, at some point, as a system of linear equations. Kirchhoff’s laws applied to a circuit of n meshes give n equations in n unknown currents. A truss, a material balance, a least-squares fit of a calibration curve and the simulation of any circuit in SPICE are, underneath, the same thing: A·x = b.

\[ \begin{array}{c} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1 n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2 n} x_n = b_2 \\ \vdots \\ a_{m 1} x_1 + a_{m 2} x_2 + \cdots + a_{m n} x_n = b_m \end{array} \] Linear means that the unknowns appear raised to the first power, with no products between them and no functions. No x², sin(x) or x·y.

The whole system is stored in the augmented matrix [A | b]: the coefficients and, separated by a bar, the column of constant terms. Working with it is working with the system.

02Three possible outcomes, and how to know which before solving

Consistent, unique solution

A single solution. With two unknowns, two lines that meet at a point.

Consistent, infinitely many solutions

Infinitely many solutions, with one or more free parameters. Two coincident lines.

Inconsistent

No solution: the equations contradict each other. Two distinct parallel lines.

The Rouché-Frobenius theorem decides which case it is by comparing the rank of A with that of the augmented matrix:

Condition	System	Solutions
\( rank(A) = rank(A\|b) = n \)	Consistent, unique solution	One
\( rank(A) = rank(A\|b) < n \)	Consistent, infinitely many solutions	Infinitely many, with n − rank free parameters
rank(A) < rank(A\|b)	Inconsistent	None

In plain terms: if reducing to echelon form produces a row of zeros in A but with a nonzero constant term —of the type “0 = 5”— the system has no solution. If the row ends up entirely zero, that equation was redundant and there are more unknowns than independent equations: there are infinitely many solutions.

03Gauss’s method, step by step

The idea is very simple: the elementary row operations —swapping two rows, multiplying one by a nonzero number, adding to one a multiple of another— do not change the solution set. They are applied until the system becomes triangular (Gauss) or until each unknown stands alone (Gauss-Jordan).

Lab · Gauss-Jordan elimination

Edit the coefficients and the column on the right. Each step shows the operation that was performed and what the augmented matrix looks like.

The pivot cannot be zero

If, on reaching a column, the diagonal element is zero, you have to swap that row with a lower one that does not have a zero there. On a computer something stronger is always done, partial pivoting: the pivot chosen is the element of largest absolute value in the column, even if the diagonal one is not zero, because dividing by small numbers amplifies roundoff error.

04What is being done, geometrically

Each equation in two unknowns is a line in the plane; in three, a plane in space. Solving the system means looking for the points that belong to all of them at once.

The three cases with two equations and two unknowns. With three unknowns, the lines become planes: the unique solution is the point where all three cross, and the infinitely many solutions can be a common line or an entire plane.

05Homogeneous systems

If all the constant terms are zero, A·x = 0, the system is homogeneous. It is never inconsistent: x = 0 always satisfies it, and it is called the trivial solution. The interesting question is whether there are others.

The condition that opens the door to eigenvalues

A homogeneous system of n equations in n unknowns has solutions other than the trivial one if and only if det(A) = 0. Exactly this is what is set up when looking for eigenvalues: det(A − λI) = 0 is forced so that the system (A − λI)·v = 0 has nontrivial solutions, which are the eigenvectors. This is covered in eigenvalues and eigenvectors.

In a circuit, the homogeneous system corresponds to turning off all the sources: if a nonzero solution also exists, the circuit can sustain currents by itself, which is what happens in an ideal oscillator or in a lossless LC circuit.

06When the computer solves it

A circuit simulator solves systems of thousands of equations, often at every analysis step, and uses neither Cramer’s rule nor the inverse. It uses LU factorization, which is Gaussian elimination stored as two triangular matrices, and it takes advantage of the matrix being sparse: almost all its elements are zero, because each node connects to only a few others.

Ill-conditioning

A system can have a unique solution and still be dangerous. If two equations are nearly parallel, a minimal change in one datum moves the solution enormously: the system is ill-conditioned. For example, with x + y = 2 and x + 1.001y = 2.001 the solution is (1, 1); if the second constant term becomes 2.002, the solution jumps to (0, 2). In a circuit this shows up, for instance, with resistances that differ by many orders of magnitude, and it is a reason why a simulation fails to converge.

07One circuit, from start to finish

Three meshes, sources of 12 V and 6 V, resistors of 4, 2, 6, 3 and 5 Ω. The Kirchhoff equations, with the mesh currents in the clockwise direction, become:

\[ \left[ \begin{array}{ccc} 6 & -2 & 0 \\ -2 & 11 & -3 \\ 0 & -3 & 8 \end{array} \right] \left[ \begin{array}{c} I_1 \\ I_2 \\ I_3 \end{array} \right] = \left[ \begin{array}{c} 12 \\ 0 \\ -6 \end{array} \right] \] On the diagonal, the sum of the resistances in each mesh; off it, the shared resistance with a minus sign. The matrix comes out symmetric again.

That is the example the lab in section 3 comes loaded with. Solving it gives I₁ ≈ 2.06 A, I₂ ≈ 0.19 A and I₃ ≈ −0.68 A (exactly 456/221, 42/221 and −150/221). The negative sign of I₃ is not an error: it means that this current flows opposite to the direction chosen when setting up the problem, and that is information, not a problem.

The same setup, with complex impedances instead of resistances, solves circuits in the sinusoidal steady state; there the numbers are complex but the method is identical. That step is covered in the vector study of alternating current.

08In the lab

Exercise 1 · From circuit to system and back

Build a three-mesh circuit, set up the system, solve it with the lab above and verify the three currents by measuring in a simulation. Check that the sum of the power delivered by the sources equals the sum of the power dissipated by the resistors.

Exercise 2 · Manufacturing the three cases

Write a 3 × 3 system that is consistent with a unique solution. Modify a single row to make it have infinitely many solutions, and then to make it inconsistent. Justify each case using the ranks.

Exercise 3 · Seeing ill-conditioning

Solve [[1, 1], [1, 1.001]]·x = [2, 2.001] and then change the second datum to 2.002. Compare the solutions and compute the determinant: very small compared with the coefficients. That is the warning sign.

09Common mistakes

Operating between columns. Elementary operations are on rows: each row is an equation. Mixing columns mixes unknowns.
Forgetting the constant term when applying an operation: the row includes the column on the right.
Dividing by a zero pivot instead of swapping rows.
Confusing “0 = 0” with “0 = 5”: the first indicates a redundant equation, the second, an inconsistent system.
Giving a single solution when there are infinitely many: if there are extra unknowns, the answer is expressed with parameters.
Misreading a negative sign in a current: it indicates the actual direction, not an arithmetic error.

10Self-assessment

A system of 4 equations in 4 unknowns has rank(A) = 3 and rank(A|b) = 3. What can be said?

It is consistent with infinitely many solutions, with 4 − 3 = 1 free parameter: infinitely many solutions that form a line.

After reducing to echelon form, the row 0 0 0 | 7 remains. What does it mean?

That the system is inconsistent: that row says 0 = 7.

Why is a homogeneous system never inconsistent?

Because x = 0 always satisfies it: the ranks of A and of the augmented matrix necessarily coincide.

Solve 2x + y = 5, x − y = 1.

Adding: 3x = 6, x = 2, y = 1. Check: 2·2 + 1 = 5 ✔ and 2 − 1 = 1 ✔.

What advantage does Gauss have over Cramer for 20 unknowns?

The cost: Gauss is on the order of n³ operations and Cramer requires computing 21 determinants, which by cofactors grows like n!. With n = 20 the difference is between instantaneous and impossible.

What is partial pivoting for if the pivot is not zero?

To avoid dividing by very small numbers, which amplify the machine’s roundoff error.

11Further reading

Stanley I. Grossman. Álgebra lineal. 6th ed., McGraw-Hill, 2008 (in Spanish). Systems, rank and Rouché-Frobenius with examples applied to electrical networks.
David C. Lay. Linear Algebra and Its Applications. 5th ed. (Spanish edition, “Álgebra lineal y sus aplicaciones”), Pearson, 2016. The book starts with systems and the reduced echelon form: the most natural order for this course.
Richard L. Burden and J. Douglas Faires. Numerical Analysis. 9th ed. (Spanish edition, “Análisis numérico”), Cengage Learning, 2011. For the numerical side: pivoting, LU factorization, condition number and roundoff errors.
Charles K. Alexander and Matthew N. O. Sadiku. Fundamentals of Electric Circuits. 5th ed. (Spanish edition, “Fundamentos de circuitos eléctricos”), McGraw-Hill, 2013. Where these systems come from: mesh and nodal analysis, with dozens of worked circuits.