Gaussian Elimination With Complex Coefficients

The common assumption is that moving from real numbers to complex numbers in Gaussian elimination simply means swapping out real arithmetic for complex arithmetic, but the change cuts deeper. When matrix entries contain real and imaginary parts, every step of row reduction changes: pivot selection now depends on the modulus of a complex number, not its real part; each elimination step requires complex multiplication, which costs four real multiplications and two real additions per operation; and the entire algorithm jumps from O(n³) to O(4n³) real operations. What changes in row reduction when matrix entries contain real and imaginary parts? It does so by working through a concrete example of gaussian elimination with complex coefficients, showing every calculation, and naming the specific failure case you must watch for.

Take the system:

(1+2i)x + (3-i)y = 7+i
(2-i)x + (4+3i)y = 6-2i

Write the augmented matrix [A|b]:

[[1+2i, 3-i, 7+i], [2-i, 4+3i, 6-2i]]

Forward elimination begins with the first pivot in row 1, column 1. In the real case you compare absolute values; here you compare moduli. The modulus of (1+2i) is √(1²+2²)=√5≈2.236. The modulus of (2-i) is √(2²+(-1)²)=√5≈2.236. They tie, so keep the first row as the pivot row. No swap needed.

Now eliminate the entry below the pivot. Compute the multiplier: (2-i)/(1+2i). Multiply numerator and denominator by the conjugate of the denominator: (2-i)(1-2i) / ((1+2i)(1-2i)). The denominator becomes 1²+2²=5. The numerator: (2)(1) + (2)(-2i) + (-i)(1) + (-i)(-2i) = 2 -4i -i +2i² = 2 -5i -2 = -5i. So the multiplier is (-5i)/5 = -i.

New row 2 = row 2 - (multiplier) × row 1. Since the multiplier is -i, row 2 = row 2 + i × row 1. Compute i × row 1: i×(1+2i, 3-i, 7+i) = (i+2i², 3i - i², 7i + i²) = (i-2, 3i+1, 7i-1). Add that to row 2: (2-i)+(i-2)=0; (4+3i)+(3i+1)=5+6i; (6-2i)+(7i-1)=5+5i.

The matrix is now in row-echelon form: [[1+2i, 3-i, 7+i], [0, 5+6i, 5+5i]].

Back-substitution starts from the last row. Solve (5+6i)y = 5+5i. Divide: y = (5+5i)/(5+6i). Multiply numerator and denominator by the conjugate of the denominator: (5+5i)(5-6i) / ((5+6i)(5-6i)). The denominator is 5²+6²=25+36=61. The numerator: (5)(5) + (5)(-6i) + (5i)(5) + (5i)(-6i) = 25 -30i +25i -30i² = 25 -5i +30 = 55 -5i. So y = (55 -5i)/61 = (55/61) - (5/61)i.

Now solve for x. From the first row: (1+2i)x + (3-i)y = 7+i. Substitute y: (3-i) × ((55-5i)/61) = (165 -15i -55i +5i²)/61 = (165 -70i -5)/61 = (160 -70i)/61. Then 7+i - (160-70i)/61 = (427+61i -160+70i)/61 = (267+131i)/61. So x = (267+131i) / (61 × (1+2i)) = (267+131i) / (61+122i). Multiply numerator and denominator by the conjugate of the denominator: (267+131i)(61-122i) / ((61+122i)(61-122i)). The denominator is 61²+122² = 3721+14884 = 18605. The numerator: 267×61 -267×122i +131i×61 -131i×122i = 16287 -32574i +7991i -15982i² = 16287 -24583i +15982 = 32269 -24583i. So x = (32269/18605) - (24583/18605)i ≈ 1.734 - 1.321i, and y ≈ 0.903 - 0.082i.

At this point, you would normally reach for a complex number calculator to verify the arithmetic, because a single sign error in any of the four complex multiplications or two complex additions per step will produce a completely different result. Checking against the original equations shows the solution works: (1+2i)(1.734-1.321i) + (3-i)(0.903-0.082i) ≈ 7.003+0.998i, and (2-i)(1.734-1.321i) + (4+3i)(0.903-0.082i) ≈ 6.005-1.995i, both within rounding of the original constants.

Three things change when you move from real to complex coefficients, and they are not optional adjustments.

Pivot Selection Uses Modulus, Not Absolute Value

In real partial pivoting you pick the row with the largest absolute value in the current column. For complex entries you must use the modulus: |a+bi| = √(a²+b²). In the example above, both pivot candidates had modulus √5, so the tie was harmless. But if one entry were (100+0i) and another (0+100i), their real parts would suggest very different pivots while their moduli are identical. Using modulus is the correct standard, and it is what every library solver (LAPACK's dgesv, NumPy's linalg.solve) implements.

Each Elimination Step Costs Four Times More

A single complex multiplication requires four real multiplications and two real additions. Every addition or subtraction of complex numbers requires two real operations. The result is that Gaussian elimination with complex coefficients runs in O(4n³) real operations instead of O(n³). For a 5×5 system that is 500 real operations versus 125, noticeable when checking by hand. For a 1000×1000 system it is the difference between seconds and hours, which is why the research notes that large sparse systems should go to scipy.sparse.linalg.splu, not to a hand-checkable calculator.

Zero Pivots Are Still Zero, But Swapping Is Not Guaranteed

A zero pivot in the complex case means the entry is 0+0i. If every entry in the current pivot column is 0+0i, no row swap can create a non-zero pivot, and the matrix is singular. This is the same as the real case, but the practical danger is different: a pivot that is non-zero but very small in modulus (e.g., 1e-20+0i) will cause the same numerical instability as a tiny real pivot. Partial pivoting by modulus mitigates this but does not eliminate it. The failure case for complex elimination is exactly the same as the real one: a row of zeros on the left paired with a non-zero on the right means no solution; a row of zeros on both sides means infinite solutions, which you must express in parametric form with free variables.

The three elementary row operations, swap, scale, add, are the only allowed operations and they do not change the solution set, whether the entries are real or complex. The augmented matrix notation [A|b] is universal. Back-substitution still proceeds from the last row upward. The number of pivot columns still equals the rank of the matrix. None of these structural facts change.

What does change is the arithmetic at every step. When you scale a row by a complex number, every entry in that row must be multiplied following complex arithmetic rules. When you add a multiple of one row to another, both the real and imaginary parts must be combined separately. A single arithmetic error in any step propagates through the rest of the elimination and into the back-substitution. This is why the worked example above recomputes every step explicitly: the cost of a mistake in complex elimination is a completely wrong solution.

Operation	Real Cost (flops)	Complex Cost (flops)
Addition/Subtraction	1	2 real flops (real and imag parts separately)
Multiplication	1	4 real multiplications + 2 real additions = 6 flops
Division	1	Multiply by conjugate, then divide: ~14 flops
Pivot selection (per column)	n comparisons	n modulus calculations (each ~5 flops)

The single most practical thing to know about Gaussian elimination with complex coefficients is this: if you are solving a system by hand, you will make an arithmetic mistake. The research shows that each complex multiplication costs four real multiplications and two real additions. For a 2×2 system like the one above, forward elimination requires one complex multiplication and two complex additions. For a 3×3 system, it jumps to six complex multiplications and nine complex additions. The error rate climbs faster than the system size.

What you should do next: before you start, write down the modulus of every complex entry in the first column so you know which pivot to choose. Then, after every row operation, verify that the new row still satisfies the original equation when combined with the previous rows. If the system is 3×3 or larger, use a solver that implements partial pivoting by modulus (NumPy's linalg.solve does this) and compare your intermediate steps against its output. The one thing that most often goes wrong is forgetting to apply the row operation to the entire augmented row, scaling the coefficient side but not the constant side, or swapping rows but not tracking which variable corresponds to which column. Label your columns. Check your augmented column. And if the modulus of any pivot is below 1e-8, expect numerical instability even if the arithmetic is exact.