Linear Algebra for Algorithms
Three unknowns, three equations: , , . You learned to solve this at school by eliminating one variable at a time. That school method, written as a loop, is Gaussian elimination, and it is one of the most useful algorithms a programmer can own. It solves systems of equations. It computes determinants, ranks and inverses. Run over the integers modulo a prime, it gives exact answers with no rounding at all. Run over bits, with XOR in place of subtraction, it becomes the XOR basis: the tool behind "maximum XOR of a subset" and "how many different XOR values can you make". Run on the Laplacian matrix of a graph, it counts spanning trees.
This lesson is linear algebra for programmers, not for mathematicians. Every idea is introduced through a small example you can check by hand, and every algorithm comes with code in four languages that was run and checked against brute force.
You will learn to:
- read a system of equations as a matrix and solve it with Gaussian elimination, including partial pivoting and why skipping it gives wrong answers,
- tell whether a system has one, no, or infinitely many solutions, and pick a solution when there are many,
- compute determinant, rank and inverse with the same loop,
- do the whole thing exactly modulo a prime ,
- build an XOR basis and answer maximum, -th smallest and counting questions about subset XORs,
- solve expected-value problems on graphs with cycles, where plain DP has no fill order,
- connect all this to PageRank, 3-D graphics, least squares and Kirchhoff's matrix-tree theorem.
This lesson assumes you know what a matrix product is (it is defined from scratch in Matrix Exponentiation, which this lesson does not repeat), basic bit operations (Bit Manipulation), and modular inverses via Fermat's little theorem (Modular Arithmetic; a one-line recap is given below).
Why this exists
Linear equations are everywhere in computing, often in disguise:
- "Expected number of steps until…" on a graph with cycles is a system of linear equations, one per state. Probability DP handles the acyclic case by filling a table; cycles need elimination.
- "Maximum XOR you can make from a subset" is a question about a vector space over the two-element field GF(2).
- "Count spanning trees" is a determinant (Kirchhoff, 1847).
- "Which page is most important?" is an eigenvector of a link matrix (PageRank).
- Every 3-D game and every browser that renders CSS transforms multiplies and inverts 4×4 matrices millions of times a second.
- Fitting a line through noisy data (least squares) is a linear system.
The algorithm is old. A method equivalent to Gaussian elimination appears in Chapter 8 ("Fangcheng", rectangular arrays) of the Chinese text The Nine Chapters on the Mathematical Art, compiled around the first century CE; Carl Friedrich Gauss used it in the early 1800s for least-squares orbit computations, and the name stuck (Grcar, "Mathematicians of Gaussian Elimination", Notices of the AMS 58(6), 2011). Its numerical behaviour on computers was analysed by von Neumann and Goldstine (1947) and by James Wilkinson, whose backward error analysis of the 1960s is the reason we know partial pivoting works in practice.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| " unknowns, linear equations", a few hundred | Gaussian elimination, |
| "answer modulo / 998244353" and a linear system | Elimination mod , inverses by Fermat |
| "expected number of steps" on a graph with cycles | One equation per state, then Gaussian elimination |
| "maximum XOR of any subset" | XOR basis, greedy from the top bit |
| "how many distinct XOR values" / "-th smallest XOR" | XOR basis: ; reduced basis + binary of |
| "number of subsets with XOR " | if is in the span, else 0 |
| "product is a perfect square" (small primes) | Exponent parity vectors over GF(2), rank |
| "toggle lights, each switch flips a set" | Linear system over GF(2) |
| "count spanning trees" | Kirchhoff: determinant of a reduced Laplacian |
| "is this set of vectors independent", "dimension of the span" | Rank via elimination |
| "inverse matrix", "undo a linear transform" | Gauss–Jordan on |
| "-th term, , linear recurrence" | Not elimination: Matrix Exponentiation |
| "importance score that depends on neighbours' scores" | Eigenvector / linear system (PageRank) |
The meta-trigger: unknowns that depend on each other linearly, with no order in which to compute them one at a time. If there is an order (a DAG), DP is simpler. If there is no order, write the equations and eliminate.
Intuition & first principles
Vectors and matrices, for programmers
A vector is a list of numbers: v = [2, 3, -1]. A matrix is a 2-D array: rows, columns, A[i][j] is the entry in row , column . Multiplying a matrix by a vector, , produces a new vector whose -th entry is the dot product of row with :
So the system , , is just with
In code we glue onto as an extra column and call the result the augmented matrix . Every algorithm in this lesson works on that one 2-D array.
A few more words you will need:
- A linear combination of vectors is for some numbers .
- Vectors are linearly independent if no one of them is a linear combination of the others.
[1, 0]and[0, 1]are independent.[1, 2]and[2, 4]are not: the second is twice the first. - The span of some vectors is the set of all their linear combinations.
- The rank of a matrix is the largest number of independent rows (equivalently, columns). It is the "true number of equations" once you remove the ones that repeat information.
- The identity matrix has 1 on the diagonal and 0 elsewhere; .
- The inverse of a square matrix, when it exists, is the matrix with . Then .
- The determinant is a single number that is zero exactly when has no inverse. For a 2×2 matrix, .
The three moves that never change the answer
You can do three things to the equations of a system without changing its set of solutions:
- Swap two equations.
- Scale an equation by a nonzero number.
- Add a multiple of one equation to another.
Each move can be undone (swap back; scale by the reciprocal; subtract the same multiple), so no solution is ever gained or lost. These are the elementary row operations. Gaussian elimination is nothing but a careful schedule of these three moves.
A tiny example you can hold in your head
and .
- Subtract 3 × (first) from the second: , i.e. , so .
- Put it back into the first: .
Step one is forward elimination: use equation 1 to remove from every equation below it. Step two is back substitution: the last equation has one unknown; solve it and walk upwards. With equations, you repeat step one for each column, then do step two once.
Row echelon form
After forward elimination the matrix has a staircase shape called row echelon form: each row's first nonzero entry (its pivot) is strictly to the right of the pivot in the row above, and all-zero rows sit at the bottom.
If you keep going, scaling each pivot to 1 and clearing the entries above each pivot too, you reach reduced row echelon form (RREF), where each pivot column is all zeros except a single 1. Reading the solution from RREF needs no back substitution. Doing it this way is called Gauss–Jordan elimination. It costs about 1.5× more arithmetic than elimination plus back substitution, but the code is shorter and it directly handles every case (one, none, infinitely many solutions), so most competitive-programming code uses it.
Mechanics
1. Gaussian elimination with partial pivoting, traced
The algorithm, for each column col from left to right:
- Choose the pivot row: among the rows not yet used, take the one whose entry in
colhas the largest absolute value. This is partial pivoting. - If that entry is (nearly) zero, the column has no pivot; skip it (its variable will be "free").
- Swap the pivot row into place.
- Eliminate: for every other row , subtract times the pivot row, which makes .
flowchart TD
S["col = 0, row = 0"] --> P["find row with largest |A[r][col]|, r >= row"]
P --> Z{"|pivot| < EPS ?"}
Z -->|"yes"| F["col is a free variable, col++"]
Z -->|"no"| W["swap pivot row into position row"]
W --> E["subtract multiples of the pivot row from the other rows"]
E --> N["row++, col++"]
F --> C{"col < m and row < n ?"}
N --> C
C -->|"yes"| P
C -->|"no"| R["read the answer, check leftover rows"]
Here is forward elimination on our 3×3 system, computed with exact fractions so you can follow every number. Each row of the table shows the augmented matrix right after the action in the first column.
| Step | Action | Row 1 | Row 2 | Row 3 |
|---|---|---|---|---|
| 0 | start | 2, 1, −1 | 8 | −3, −1, 2 | −11 | −2, 1, 2 | −3 |
| 1 | column 0: largest |entry| is −3 (row 2); swap rows 1 and 2 | −3, −1, 2 | −11 | 2, 1, −1 | 8 | −2, 1, 2 | −3 |
| 2 | row 2 −= (−2/3) · row 1 | −3, −1, 2 | −11 | 0, 1/3, 1/3 | 2/3 | −2, 1, 2 | −3 |
| 3 | row 3 −= (2/3) · row 1 | −3, −1, 2 | −11 | 0, 1/3, 1/3 | 2/3 | 0, 5/3, 2/3 | 13/3 |
| 4 | column 1: |5/3| > |1/3|; swap rows 2 and 3 | −3, −1, 2 | −11 | 0, 5/3, 2/3 | 13/3 | 0, 1/3, 1/3 | 2/3 |
| 5 | row 3 −= (1/5) · row 2 | −3, −1, 2 | −11 | 0, 5/3, 2/3 | 13/3 | 0, 0, 1/5 | −1/5 |
| 6 | column 2: only candidate is 1/5; no swap | −3, −1, 2 | −11 | 0, 5/3, 2/3 | 13/3 | 0, 0, 1/5 | −1/5 |
Back substitution, bottom to top:
- Row 3: , so .
- Row 2: , so , .
- Row 1: , so , .
Answer . Check in the original second equation: ✔.
2. Why partial pivoting: a two-line disaster
Without pivoting you would take whatever entry happens to sit on the diagonal. Mathematically that is fine as long as it is not exactly zero. On a computer it can be a catastrophe. Take
The true solution is extremely close to , . Now eliminate without pivoting, in IEEE double precision:
- Multiplier .
- New second row: -coefficient , right side . In doubles both round to , because swamps the 1 and the 2 (a double carries about 16 significant digits).
- So — still fine. But then .
The program prints , . That is not a little inaccurate; it is completely wrong. With partial pivoting the algorithm first swaps the rows (because ), the multiplier becomes , nothing is swamped, and the result is , . Both runs were checked in Python.
The rule behind this: a small pivot means a large multiplier, and a large multiplier blows up rounding errors that were tiny a moment ago. Choosing the largest available pivot keeps every multiplier at most 1 in absolute value. Wilkinson proved that with partial pivoting the computed answer is the exact answer of a slightly perturbed system (backward stability), with a growth factor that can in theory reach but in practice almost never does (Trefethen and Bau, Numerical Linear Algebra, Lecture 22). Full pivoting (search the whole remaining submatrix for the largest entry, swap rows and columns) is even safer but costs searching per step and is rarely needed.
Pivoting is about numerics, not correctness in exact arithmetic
With exact numbers (fractions, or integers mod ), any nonzero pivot is equally good. That is why the mod- code below takes the first nonzero entry, not the largest. Partial pivoting is only for floating point.
3. One, none, or infinitely many solutions
After Gauss–Jordan, look at what is left:
- Unique — every column has a pivot. Each variable is read off its pivot row.
- None — some row became with . The equations contradict each other.
- Infinite — the system is consistent but some column has no pivot. That variable is free: pick any value, and the pivot variables follow. The code sets every free variable to 0 and returns that particular solution.
flowchart TD
A["Gauss-Jordan done"] --> B{"a row reads 0 = c, c != 0 ?"}
B -->|"yes"| N["NO solution"]
B -->|"no"| C{"every column has a pivot ?"}
C -->|"yes"| U["UNIQUE solution"]
C -->|"no"| I["INFINITELY many: free variables can be anything"]
Two 2×2 examples:
- , . Subtract 2 × row 1: . No solution (two parallel lines).
- , . Subtract 2 × row 1: . Column has no pivot, so is free; with we get . Infinitely many: every .
In terms of rank: a system with unknowns is solvable iff , and then the solutions form a family with free parameters (the Rouché–Capelli theorem). Over a finite field with elements, that means exactly solutions, a fact the tests below check by brute force.
4. Determinant and rank, for free
The determinant obeys three rules that match the three row moves:
| Row move | Effect on |
|---|---|
| swap two rows | multiplies it by |
| scale a row by | multiplies it by |
| add a multiple of one row to another | no change |
And the determinant of a triangular matrix is the product of its diagonal. So: run forward elimination (swaps and "add a multiple" only), multiply the pivots, and flip the sign once per swap. For our system, the pivots were , , , and there were 2 swaps:
Direct cofactor expansion agrees: ✔. If some column has no pivot, the determinant is 0.
The rank is simply the number of pivots found. A square matrix is invertible iff its rank is iff its determinant is nonzero.
Never compute determinants by cofactor expansion in code
Expanding along a row is : 20! is . Elimination is : 8,000 steps for .
5. The inverse by Gauss–Jordan
To invert , write the identity next to it, , and run Gauss–Jordan until the left half becomes . The right half is then . Why: the row moves amount to multiplying on the left by some invertible matrix . If then , and the right half, which started as , is now .
Example, (determinant 1), with partial pivoting:
| After column | Left half | Right half |
|---|---|---|
| start | 1, 2, 3 / 0, 1, 4 / 5, 6, 0 | 1, 0, 0 / 0, 1, 0 / 0, 0, 1 |
| 0 (swap rows 1 and 3, scale by 1/5, clear) | 1, 6/5, 0 / 0, 1, 4 / 0, 4/5, 3 | 0, 0, 1/5 / 0, 1, 0 / 1, 0, −1/5 |
| 1 (pivot 1, clear above and below) | 1, 0, −24/5 / 0, 1, 4 / 0, 0, −1/5 | 0, −6/5, 1/5 / 0, 1, 0 / 1, −4/5, −1/5 |
| 2 (scale by −5, clear) | 1, 0, 0 / 0, 1, 0 / 0, 0, 1 | −24, 18, 5 / 20, −15, −4 / −5, 4, 1 |
So . Multiply it by and you get .
In practice you rarely need the inverse itself. To solve for many different , factor once (the LU decomposition: elimination records its multipliers in and leaves upper triangular) and then each new costs only . LAPACK's dgesv and NumPy's numpy.linalg.solve do exactly this, with partial pivoting.
6. Elimination modulo a prime: exact answers
Many counting problems want "the answer modulo " for a prime like or . The integers modulo a prime form a field: you can add, subtract, multiply, and divide by any nonzero number. Division is multiplication by the modular inverse, and Fermat's little theorem gives it: for , , so , computed by fast exponentiation in .
Because a field has division, every step of Gaussian elimination works unchanged. Two differences:
- There is no rounding, so "is this zero?" is an exact test. No EPS anywhere.
- Any nonzero pivot is fine; there is no "largest".
Example modulo 7: , .
- Row 2 −= 3 × row 1: , i.e. , i.e. .
- (because ). So .
- .
Answer ; check: ✔ and ✔. (Over the rationals the same system has , ; .)
Elimination mod only works when is prime
Modulo a composite number like or , some nonzero numbers (for example 2 mod ) have no inverse, and the algorithm can get stuck. For determinants modulo an arbitrary , use a Euclid-style elimination that subtracts rows like the gcd algorithm, , or compute modulo several primes and combine with the Chinese Remainder Theorem (Advanced Number Theory).
Also be careful when the true answer is a rational number, like an expected value of . "Modulo " then means . Elimination mod computes exactly that, provided the system's determinant is not divisible by — for and modest inputs that is very unlikely, and problems that ask for an answer mod usually guarantee it.
7. The XOR basis: linear algebra over bits
Now replace numbers with bits. The field GF(2) has two elements, 0 and 1. Addition is XOR (), multiplication is AND. A -bit integer is a vector of bits, and XOR of two integers is vector addition. Every rule from above still holds; only the arithmetic changed.
A question like "what is the maximum XOR of any subset of [12, 9, 7, 5, 14]?" is about the span of these vectors: the set of all subset XORs. Gaussian elimination over GF(2) builds a compact description of that span, called a linear basis or XOR basis:
b[i]is either 0 or a vector whose highest set bit is .- To insert : scan bits from high to low. At the first set bit : if
b[i]is empty, store there and stop. Otherwise (this clears bit ) and keep scanning. If becomes 0, it was already in the span.
This is forward elimination, one row at a time: each stored vector is a pivot row, and XOR is "subtract a multiple of the pivot row" (over GF(2), the only multiples are 0 and 1).
Trace with 4-bit values [12, 9, 7, 5, 14]:
| Insert | Binary | Steps | b[3] | b[2] | b[1] | b[0] | Result |
|---|---|---|---|---|---|---|---|
| 12 | 1100 | bit 3 empty → store | 1100 | – | – | – | new |
| 9 | 1001 | bit 3: ^ 1100 → 0101; bit 2 empty → store | 1100 | 0101 | – | – | new |
| 7 | 0111 | bit 2: ^ 0101 → 0010; bit 1 empty → store | 1100 | 0101 | 0010 | – | new |
| 5 | 0101 | bit 2: ^ 0101 → 0000 | 1100 | 0101 | 0010 | – | dependent |
| 14 | 1110 | bit 3: ^ 1100 → 0010; bit 1: ^ 0010 → 0000 | 1100 | 0101 | 0010 | – | dependent |
The basis has 3 vectors, so the rank is 3. Indeed 5 = 12 ⊕ 9 and 14 = 9 ⊕ 7: they add nothing new to the span.
What you can answer with it:
- Is a subset XOR? Reduce by the basis like an insertion; it is representable iff it reaches 0.
- How many distinct subset XORs? Exactly , counting the empty subset's 0. Every subset of the basis gives a different XOR (the highest bit of the topmost chosen vector cannot be cancelled), and every subset XOR of the input is some subset XOR of the basis. Here ; brute force over all subsets finds the 8 values
0, 2, 5, 7, 9, 11, 12, 14. - Maximum subset XOR: start with
res = 0; for from high to low, ifres ^ b[i] > resthenres ^= b[i]. Here: 0 → 1100 (12) → 1100 ^ 0101 = 1001 is smaller, skip → 1100 ^ 0010 = 1110 (14). Maximum 14 ✔. The greedy is right because bit of the result can only be changed byb[i]and the vectors above it, which were already decided. - Number of subsets (of the original numbers) with XOR equal to : if is representable, else 0. Each of the dependent elements can be included or not freely; the basis part is then forced. Here subsets give each of the 8 values: ✔.
- -th smallest subset XOR: first reduce the basis so that each pivot bit appears in exactly one vector (for each
b[i], XOR it out of every higherb[j]that has bit set). Hereb[3]= 1100 has bit 2 set, so it becomes 1100 ^ 0101 = 1001: the reduced basis is{0010, 0101, 1001}={2, 5, 9}. Now the vectors behave like binary digits: the -th smallest (0-indexed) is the XOR of the reduced vectors selected by the bits of . For :0, 2, 5, 7, 9, 11, 12, 14— the sorted list exactly ✔.
"Non-empty subsets"
Many problems forbid the empty subset. Then 0 is achievable iff some element was dependent (). Adjust (and the count) by one accordingly.
The XOR basis also explains a classic trick on graphs: the XOR of any path between two vertices equals the XOR of one fixed path plus some XOR of cycle values, so "minimum XOR path" = reduce one path's XOR by the basis of all cycle XORs (Codeforces 845G, in the practice ladder). For more bit tricks, see Bit Manipulation.
8. Expected values on graphs with cycles
Probability DP computes expected values by filling a table backwards from the goal. That needs an order: each state must depend only on states already computed. On a graph with cycles there is no such order, but every state still gives one linear equation. Solve them together.
Example: a random walk on the graph with edges 0–1, 1–2, 2–0, 2–3. A token starts at vertex 0 and moves to a uniformly random neighbour each step. How many steps, on average, until it reaches vertex 3?
flowchart LR
v0(("0")) --- v1(("1"))
v1 --- v2(("2"))
v2 --- v0
v2 --- v3(("3 target"))
Let be the expected number of steps from ; . From each other vertex you take one step and land on a neighbour:
Move the unknowns to the left:
| rhs | ||||
|---|---|---|---|---|
| eq. 0 | 1 | −1/2 | −1/2 | 1 |
| eq. 1 | −1/2 | 1 | −1/2 | 1 |
| eq. 2 | −1/3 | −1/3 | 1 | 1 |
Gaussian elimination gives , , . Sanity check: ✔. A simulation of 200,000 walks averaged 9.01.
The general recipe:
- One unknown per non-absorbing state.
- For each state: (usually 1 step).
- Absorbing states have and are left out (their terms vanish).
- Solve with doubles (with pivoting) or, if the answer is wanted mod , with elimination mod .
Check that the goal is reachable
If some state can never reach an absorbing state, its expected time is infinite and the matrix is singular — elimination will report "infinitely many" or "no" solutions, or, with doubles, garbage. Run a BFS backwards from the goal first and drop unreachable states.
For states this is : fine for or so. For large sparse chains use value iteration (repeat until it stops changing), as in Probability DP. When the equations are tridiagonal (each state links only to its neighbours on a line), elimination takes (the Thomas algorithm), which is the trick behind Codeforces 24D in the practice ladder.
9. Matrix exponentiation, in one paragraph
When the same linear step is applied many times — — you do not eliminate; you raise to a power by repeated squaring, in for a matrix. Fibonacci in , counting walks of length , Markov chains after steps and transfer-matrix tilings all live there. The full lesson is Matrix Exponentiation. The two techniques meet in one place: the long-run behaviour of is governed by the eigenvectors of , which brings us to PageRank.
Applications
PageRank: an eigenvector you can solve for
PageRank models a "random surfer": on each click, with probability (the damping factor, 0.85 in the original paper) the surfer follows a random outgoing link, otherwise jumps to a uniformly random page. The rank of page is the long-run fraction of time spent there:
In matrix form, , where if links to . Because the entries of sum to 1, this is the same as for the "Google matrix" : is the eigenvector of with eigenvalue 1. Equivalently, it is the solution of the linear system .
Three pages: 0 links to 1 and 2, 1 links to 2, 2 links to 0. With , exact elimination gives
Page 2, with two incoming links, ranks highest; page 1, linked only by half of page 0's vote, ranks lowest. Power iteration (start at and apply the formula repeatedly) reaches the same numbers to 4 decimals within 20 iterations: after 1, 5, 10 and 20 iterations the first entry is 0.3333, 0.3949, 0.3889, 0.3878.
At web scale, nobody runs Gaussian elimination: is billions and is absurd. The matrix is extremely sparse, so power iteration (one sparse matrix–vector product per round, error shrinking roughly like ) is the method described by Page, Brin, Motwani and Winograd ("The PageRank Citation Ranking: Bringing Order to the Web", Stanford tech report, 1999); Langville and Meyer's Google's PageRank and Beyond (2006) covers the linear-algebra view in depth. More on how search engines use it: Search & Recommendation.
Graphics: 4×4 matrices everywhere
Every vertex in a 3-D scene is multiplied by a chain of matrices: model (place the object), view (place the camera), projection (perspective). Translations are not linear in 3-D, so graphics uses homogeneous coordinates: the point becomes and a translation becomes a 4×4 matrix. Composing transforms is multiplying matrices; undoing one (the view matrix is the inverse of the camera's placement) is inverting. Surface normals are transformed by the inverse transpose of the model matrix, so that they stay perpendicular after non-uniform scaling. OpenGL, Direct3D, Vulkan, WebGL and CSS transform: matrix3d(...) all expose exactly these 4×4 matrices (the matrix3d() function in the CSS Transforms Module Level 2 specification takes 16 values in column-major order). Libraries like GLM implement the 4×4 inverse with a closed-form cofactor (adjugate) formula rather than a pivoting loop: is fixed, and the unrolled formula has no branches.
Least squares
With more equations than unknowns (fitting a line to 1,000 noisy points), usually has no exact solution. The least-squares solution minimises and satisfies the normal equations , a square system you can hand to Gaussian elimination. That is fine for small, well-behaved problems, but it squares the condition number (the factor by which input errors can be amplified), so numerical libraries use a QR decomposition or the SVD instead: numpy.linalg.lstsq calls LAPACK's SVD-based gelsd. Gauss himself developed least squares for predicting the orbit of the asteroid Ceres (1801), which is how elimination got his name.
Kirchhoff's matrix-tree theorem: counting spanning trees
A spanning tree of a connected graph is a subset of its edges that connects all vertices without forming a cycle (Minimum Spanning Trees finds the cheapest one). How many are there? Build the Laplacian : is the diagonal matrix of degrees and the adjacency matrix. Kirchhoff's theorem (1847): delete any one row and the same column of ; the determinant of what remains is the number of spanning trees.
Example, the "kite" on 4 vertices with edges 0–1, 0–2, 1–2, 1–3, 2–3 (a square with one diagonal):
flowchart LR
k0(("0")) --- k1(("1"))
k0 --- k2(("2"))
k1 --- k2
k1 --- k3(("3"))
k2 --- k3
(Row and column 0 deleted.) Brute force agrees: of the ways to choose 3 edges, exactly 2 contain a cycle (the triangles 0–1–2 and 1–2–3), leaving 8 spanning trees. For the complete graph the theorem gives Cayley's formula : 16 for , 125 for . All of these, plus 200 random graphs with up to 6 vertices, were checked against brute-force enumeration with a union-find (Union-Find).
The counts grow fast, so contest problems ask for them modulo a prime: run det_mod on the reduced Laplacian. Variants: multigraphs (put edge multiplicities in ), weighted counts (sum over trees of the product of edge weights: put weights in ), and directed graphs (the number of spanning arborescences rooted at uses in-degrees and deletes row and column ; Tutte's version of the theorem).
The ladder: brute force → better → optimal
Problem: solve an system .
Rung 1: Cramer's rule with cofactor determinants —
, where is with column replaced by . Elegant on paper; with cofactor expansion each determinant costs . For that is already about operations; for , hopeless.
Rung 2: Gaussian elimination without pivoting —
About multiply–adds for forward elimination plus for back substitution. is roughly operations: under a second in C++. But it crashes on a zero pivot that a swap would fix, and it gives garbage on tiny pivots (Mechanics §2).
Rung 3: Gaussian elimination with partial pivoting — , numerically sound
Same cost plus comparisons in total. This is what LAPACK's dgesv does (as an LU factorisation, blocked for cache efficiency). For exact problems, replace doubles with arithmetic mod (no pivot search needed) or with fractions (exact but the numbers grow; Bareiss's fraction-free variant keeps integer entries polynomially bounded).
Rung 4: exploit structure
- Over GF(2): pack each row into machine words (a bitset). Eliminating one row is word XORs, so the whole thing is : in well under a second.
- Tridiagonal / banded: or for bandwidth .
- Sparse and huge: iterative methods (Jacobi, Gauss–Seidel, conjugate gradient, power iteration) that never form the full matrix.
- Theory: Strassen-style fast matrix multiplication gives elimination in with ; not used for practical sizes.
| Method | Time | Exact? | When |
|---|---|---|---|
| Cramer + cofactors | yes | never in code; by hand | |
| Elimination, no pivoting | in exact arithmetic | mod , fractions | |
| Elimination, partial pivoting | no (floating point), backward stable | doubles, general use | |
| Bitset elimination over GF(2) | yes | XOR systems, up to a few thousand | |
| XOR basis (incremental) | per insert, bits | yes | streams of numbers, subset-XOR queries |
| Thomas algorithm | no | tridiagonal systems | |
| Iterative (power, Gauss–Seidel) | per round | approximate | huge sparse systems |
Correctness
Row operations preserve the solution set. Each operation is left-multiplication by an invertible elementary matrix . If then ; conversely, if then multiplying by gives back . So the final system has exactly the same solutions as the original.
The loop reaches (reduced) row echelon form. Invariant: after processing columns , the rows each have a pivot in a distinct column , every other entry in those pivot columns is 0, and the rows are zero in columns . Processing column either finds no nonzero entry in rows (the invariant holds with and no new pivot), or swaps one up, and the elimination step zeroes column everywhere else without touching columns (the pivot row is zero there, except in its own pivot column, which is already zero in the other rows). By induction on , at the end the matrix is in RREF.
Reading the answer is right. In RREF, a row with all-zero coefficients and a nonzero right side is the equation : no solution. Otherwise each pivot row says "pivot variable + (combination of free variables) = value"; any choice of free variables gives a solution, and choosing 0 gives the one the code returns.
Determinant. Forward elimination uses only swaps (each flips the sign) and "add a multiple" (no change), and ends with an upper-triangular matrix whose determinant is the product of the diagonal. Both facts follow from the determinant being multilinear and alternating in the rows.
XOR basis. Invariant: the nonzero b[i] are independent (distinct highest bits — no XOR of a non-empty subset of them can be 0, because the highest of their leading bits survives) and their span equals the span of all inserted numbers (inserting either stores reduced by basis vectors — a combination of and existing vectors, so the span gains exactly — or reduces to 0, proving was already in the span). The max-XOR greedy is correct by induction from the top bit down: among the basis vectors not yet decided, b[i] is the only one that can change bit (all others have lower leading bits), so the choice at step is forced if we want bit to be 1 — and a 1 at bit beats any pattern of lower bits. Whatever b[i] does to lower bits is fixed up by later steps.
Matrix-tree theorem. Proof sketch: the Laplacian factors as , where is the signed vertex–edge incidence matrix. Deleting row gives , and the Cauchy–Binet formula expands as a sum over -edge subsets of . That determinant is if is a spanning tree and 0 otherwise. Full proof: Aigner and Ziegler, Proofs from THE BOOK, chapter "Cayley's formula for the number of trees".
Complexity
| Operation | Time | Space |
|---|---|---|
| Gaussian / Gauss–Jordan elimination, | ; square | (in place) |
| Determinant, rank | ||
| Inverse via | ||
| Elimination mod | (one inverse per pivot) | |
| GF(2) elimination with bitsets | , | words |
| XOR basis: insert, query, max | , = number of bits | |
| XOR basis: -th smallest | to reduce once, then per query | |
| Expected values, states | ||
| Spanning trees, vertices |
The constant matters: Gaussian elimination does about multiply-adds, Gauss–Jordan about . Best, average and worst case are all for dense matrices; early exits only happen for singular ones. Memory access is row-wise, so store rows contiguously.
Implementation
Each block contains three parts: (1) Gauss–Jordan elimination over doubles with partial pivoting, returning the number of solutions and one solution, plus a determinant; (2) exact elimination modulo a prime, a modular determinant, and Kirchhoff's spanning-tree count; (3) an XOR basis with insert, membership, maximum, count and -th smallest. Each main checks the examples from this lesson and then runs 300 random systems against brute force (every vector mod 5) and 300 random XOR bases against enumeration of all subsets. All four programs printed all linear-algebra tests passed.
import itertools
import random
from typing import List, Tuple
EPS = 1e-9
NONE, UNIQUE, INFINITE = 0, 1, 2 # how many solutions a system has
# ---------- 1. Gaussian elimination over doubles, partial pivoting ----------
def gauss(a: List[List[float]], b: List[float]) -> Tuple[int, List[float]]:
"""Solve a·x = b (n equations, m unknowns). Returns (status, x).
For INFINITE, x is one solution with every free variable set to 0."""
n, m = len(a), len(a[0])
M = [[float(v) for v in row] + [float(bi)] for row, bi in zip(a, b)]
where = [-1] * m # where[col] = row that holds col's pivot
row = 0
for col in range(m):
if row == n:
break
piv = max(range(row, n), key=lambda r: abs(M[r][col])) # partial pivoting
if abs(M[piv][col]) < EPS:
continue # no usable pivot: col is a free variable
M[row], M[piv] = M[piv], M[row]
where[col] = row
for r in range(n): # Gauss-Jordan: clear the column above and below
if r != row:
f = M[r][col] / M[row][col]
if f != 0.0:
for c in range(col, m + 1):
M[r][c] -= f * M[row][c]
row += 1
x = [0.0] * m
for col in range(m):
if where[col] != -1:
x[col] = M[where[col]][m] / M[where[col]][col]
for r in range(n): # a leftover row 0 = nonzero means no solution
if abs(sum(M[r][c] * x[c] for c in range(m)) - M[r][m]) > EPS:
return NONE, []
if -1 in where:
return INFINITE, x
return UNIQUE, x
def determinant(a: List[List[float]]) -> float:
n = len(a)
M = [[float(v) for v in row] for row in a]
det = 1.0
for col in range(n):
piv = max(range(col, n), key=lambda r: abs(M[r][col]))
if abs(M[piv][col]) < EPS:
return 0.0
if piv != col:
M[col], M[piv] = M[piv], M[col]
det = -det # a row swap flips the sign
det *= M[col][col]
for r in range(col + 1, n):
f = M[r][col] / M[col][col]
for c in range(col, n):
M[r][c] -= f * M[col][c]
return det
# ---------- 2. Exact elimination modulo a prime p ----------
def gauss_mod(a: List[List[int]], b: List[int], p: int) -> Tuple[int, List[int], int]:
"""Solve a·x = b (mod p), p prime. Returns (status, x, rank)."""
n, m = len(a), len(a[0])
M = [[v % p for v in row] + [bi % p] for row, bi in zip(a, b)]
where = [-1] * m
row = 0
for col in range(m):
if row == n:
break
piv = next((r for r in range(row, n) if M[r][col] != 0), -1)
if piv == -1:
continue # exact arithmetic: any nonzero pivot will do
M[row], M[piv] = M[piv], M[row]
where[col] = row
inv = pow(M[row][col], p - 2, p) # Fermat inverse
M[row] = [v * inv % p for v in M[row]] # make the pivot 1
for r in range(n):
if r != row and M[r][col] != 0:
f = M[r][col]
M[r] = [(v - f * w) % p for v, w in zip(M[r], M[row])]
row += 1
rank = row
for r in range(rank, n): # rows with all-zero coefficients
if M[r][m] != 0:
return NONE, [], rank
x = [0] * m
for col in range(m):
if where[col] != -1:
x[col] = M[where[col]][m]
return (INFINITE if rank < m else UNIQUE), x, rank
def det_mod(a: List[List[int]], p: int) -> int:
n = len(a)
M = [[v % p for v in row] for row in a]
det = 1
for col in range(n):
piv = next((r for r in range(col, n) if M[r][col] != 0), -1)
if piv == -1:
return 0
if piv != col:
M[col], M[piv] = M[piv], M[col]
det = -det
det = det * M[col][col] % p
inv = pow(M[col][col], p - 2, p)
for r in range(col + 1, n):
f = M[r][col] * inv % p
if f:
M[r] = [(v - f * w) % p for v, w in zip(M[r], M[col])]
return det % p
def count_spanning_trees(n: int, edges: List[Tuple[int, int]], p: int) -> int:
"""Kirchhoff: any cofactor of the Laplacian (here: drop row/col 0)."""
L = [[0] * n for _ in range(n)]
for u, v in edges:
L[u][u] += 1
L[v][v] += 1
L[u][v] -= 1
L[v][u] -= 1
return det_mod([row[1:] for row in L[1:]], p) if n > 1 else 1
# ---------- 3. XOR basis (linear basis over GF(2)) ----------
class XorBasis:
def __init__(self, bits: int = 60):
self.bits = bits
self.b = [0] * bits # b[i] is 0 or a vector whose highest set bit is i
self.rank = 0
def insert(self, x: int) -> bool:
"""Add x; returns False if x was already a XOR of earlier vectors."""
for i in reversed(range(self.bits)):
if not (x >> i) & 1:
continue
if self.b[i] == 0:
self.b[i] = x
self.rank += 1
return True
x ^= self.b[i]
return False
def can_make(self, x: int) -> bool:
for i in reversed(range(self.bits)):
if (x >> i) & 1 and self.b[i]:
x ^= self.b[i]
return x == 0
def max_xor(self) -> int:
res = 0
for i in reversed(range(self.bits)):
if (res ^ self.b[i]) > res:
res ^= self.b[i]
return res
def count(self) -> int:
return 1 << self.rank # distinct subset XORs, empty subset included
def kth_smallest(self, k: int) -> int:
"""k-th smallest distinct subset XOR, 0-indexed (k = 0 gives 0)."""
if k >= self.count():
return -1
r = self.b[:]
for i in range(self.bits): # reduce: each pivot bit appears in one vector only
if r[i]:
for j in range(i + 1, self.bits):
if (r[j] >> i) & 1:
r[j] ^= r[i]
vecs = [v for v in r if v] # ascending by leading bit
res = 0
for t, v in enumerate(vecs):
if (k >> t) & 1:
res ^= v
return res
if __name__ == "__main__":
# Lesson examples
st, x = gauss([[2, 1, -1], [-3, -1, 2], [-2, 1, 2]], [8, -11, -3])
assert st == UNIQUE and all(abs(xi - e) < 1e-9 for xi, e in zip(x, [2, 3, -1]))
assert gauss([[1, 1], [2, 2]], [3, 7])[0] == NONE
st, x = gauss([[1, 1], [2, 2]], [3, 6])
assert st == INFINITE and x == [3.0, 0.0]
assert abs(determinant([[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]) + 1) < 1e-9
assert gauss_mod([[1, 2], [3, 4]], [3, 5], 7)[1] == [6, 2]
assert count_spanning_trees(4, [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)], 10**9 + 7) == 8
assert count_spanning_trees(5, list(itertools.combinations(range(5), 2)), 10**9 + 7) == 125
xb = XorBasis(4)
assert [xb.insert(v) for v in [12, 9, 7, 5, 14]] == [True, True, True, False, False]
assert xb.max_xor() == 14 and xb.count() == 8
assert [xb.kth_smallest(k) for k in range(8)] == [0, 2, 5, 7, 9, 11, 12, 14]
# Random checks against brute force
rng = random.Random(1)
for _ in range(300): # doubles: check a·x == b, or that brute force agrees on NONE
n = rng.randint(1, 5)
a = [[rng.randint(-5, 5) for _ in range(n)] for _ in range(n)]
b = [rng.randint(-5, 5) for _ in range(n)]
st, x = gauss(a, b)
if st != NONE:
assert all(abs(sum(a[i][j] * x[j] for j in range(n)) - b[i]) < 1e-6 for i in range(n))
p = 5 # same system mod 5, brute force over all 5^n vectors
sols = [v for v in itertools.product(range(p), repeat=n)
if all(sum(a[i][j] * v[j] for j in range(n)) % p == b[i] % p for i in range(n))]
stp, xp, rank = gauss_mod(a, b, p)
assert len(sols) == (0 if stp == NONE else p ** (n - rank))
if stp != NONE:
assert tuple(xp) in sols
dp = det_mod(a, p)
assert (dp == 0) == (rank < n)
assert round(determinant(a)) % p == dp
for _ in range(300):
vals = [rng.randrange(64) for _ in range(rng.randint(1, 7))]
xb = XorBasis(6)
for v in vals:
xb.insert(v)
subset_xors = set()
for mask in range(1 << len(vals)):
acc = 0
for i, v in enumerate(vals):
if mask >> i & 1:
acc ^= v
subset_xors.add(acc)
srt = sorted(subset_xors)
assert xb.count() == len(srt) and xb.max_xor() == srt[-1]
assert [xb.kth_smallest(k) for k in range(len(srt))] == srt
assert all(xb.can_make(v) == (v in subset_xors) for v in range(64))
print("all linear-algebra tests passed")
import java.util.*;
public class Main {
static final double EPS = 1e-9;
static final int NONE = 0, UNIQUE = 1, INFINITE = 2;
// ---------- 1. Gaussian elimination over doubles, partial pivoting ----------
/** Solves a·x = b. Writes one solution into x (free variables = 0); returns the status. */
static int gauss(double[][] a, double[] b, double[] x) {
int n = a.length, m = a[0].length;
double[][] M = new double[n][m + 1];
for (int i = 0; i < n; i++) {
System.arraycopy(a[i], 0, M[i], 0, m);
M[i][m] = b[i];
}
int[] where = new int[m];
Arrays.fill(where, -1);
int row = 0;
for (int col = 0; col < m && row < n; col++) {
int piv = row;
for (int r = row + 1; r < n; r++)
if (Math.abs(M[r][col]) > Math.abs(M[piv][col])) piv = r; // partial pivoting
if (Math.abs(M[piv][col]) < EPS) continue; // free variable
double[] t = M[row]; M[row] = M[piv]; M[piv] = t;
where[col] = row;
for (int r = 0; r < n; r++) {
if (r == row) continue;
double f = M[r][col] / M[row][col];
if (f == 0.0) continue;
for (int c = col; c <= m; c++) M[r][c] -= f * M[row][c];
}
row++;
}
Arrays.fill(x, 0.0);
for (int col = 0; col < m; col++)
if (where[col] != -1) x[col] = M[where[col]][m] / M[where[col]][col];
for (int r = 0; r < n; r++) {
double s = 0;
for (int c = 0; c < m; c++) s += M[r][c] * x[c];
if (Math.abs(s - M[r][m]) > EPS) return NONE;
}
for (int col = 0; col < m; col++) if (where[col] == -1) return INFINITE;
return UNIQUE;
}
static double determinant(double[][] a) {
int n = a.length;
double[][] M = new double[n][];
for (int i = 0; i < n; i++) M[i] = a[i].clone();
double det = 1;
for (int col = 0; col < n; col++) {
int piv = col;
for (int r = col + 1; r < n; r++)
if (Math.abs(M[r][col]) > Math.abs(M[piv][col])) piv = r;
if (Math.abs(M[piv][col]) < EPS) return 0;
if (piv != col) { double[] t = M[col]; M[col] = M[piv]; M[piv] = t; det = -det; }
det *= M[col][col];
for (int r = col + 1; r < n; r++) {
double f = M[r][col] / M[col][col];
for (int c = col; c < n; c++) M[r][c] -= f * M[col][c];
}
}
return det;
}
// ---------- 2. Exact elimination modulo a prime p ----------
static long power(long b, long e, long p) {
long r = 1; b %= p;
while (e > 0) { if ((e & 1) == 1) r = r * b % p; b = b * b % p; e >>= 1; }
return r;
}
static long mod(long v, long p) { return ((v % p) + p) % p; }
/** Solves a·x = b (mod p). Returns {status, rank}; writes x. */
static int[] gaussMod(long[][] a, long[] b, long p, long[] x) {
int n = a.length, m = a[0].length;
long[][] M = new long[n][m + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) M[i][j] = mod(a[i][j], p);
M[i][m] = mod(b[i], p);
}
int[] where = new int[m];
Arrays.fill(where, -1);
int row = 0;
for (int col = 0; col < m && row < n; col++) {
int piv = -1;
for (int r = row; r < n; r++) if (M[r][col] != 0) { piv = r; break; }
if (piv == -1) continue;
long[] t = M[row]; M[row] = M[piv]; M[piv] = t;
where[col] = row;
long inv = power(M[row][col], p - 2, p);
for (int c = 0; c <= m; c++) M[row][c] = M[row][c] * inv % p;
for (int r = 0; r < n; r++) {
if (r == row || M[r][col] == 0) continue;
long f = M[r][col];
for (int c = 0; c <= m; c++) M[r][c] = mod(M[r][c] - f * M[row][c], p);
}
row++;
}
int rank = row;
for (int r = rank; r < n; r++) if (M[r][m] != 0) return new int[]{NONE, rank};
Arrays.fill(x, 0);
for (int col = 0; col < m; col++) if (where[col] != -1) x[col] = M[where[col]][m];
return new int[]{rank < m ? INFINITE : UNIQUE, rank};
}
static long detMod(long[][] a, long p) {
int n = a.length;
long[][] M = new long[n][n];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) M[i][j] = mod(a[i][j], p);
long det = 1;
for (int col = 0; col < n; col++) {
int piv = -1;
for (int r = col; r < n; r++) if (M[r][col] != 0) { piv = r; break; }
if (piv == -1) return 0;
if (piv != col) { long[] t = M[col]; M[col] = M[piv]; M[piv] = t; det = p - det; }
det = det * M[col][col] % p;
long inv = power(M[col][col], p - 2, p);
for (int r = col + 1; r < n; r++) {
long f = M[r][col] * inv % p;
if (f == 0) continue;
for (int c = col; c < n; c++) M[r][c] = mod(M[r][c] - f * M[col][c], p);
}
}
return det % p;
}
static long countSpanningTrees(int n, int[][] edges, long p) {
if (n == 1) return 1;
long[][] L = new long[n][n];
for (int[] e : edges) { L[e[0]][e[0]]++; L[e[1]][e[1]]++; L[e[0]][e[1]]--; L[e[1]][e[0]]--; }
long[][] minor = new long[n - 1][n - 1];
for (int i = 1; i < n; i++) for (int j = 1; j < n; j++) minor[i - 1][j - 1] = L[i][j];
return detMod(minor, p);
}
// ---------- 3. XOR basis (linear basis over GF(2)) ----------
static class XorBasis {
final int bits;
final long[] b;
int rank = 0;
XorBasis(int bits) { this.bits = bits; this.b = new long[bits]; }
boolean insert(long x) {
for (int i = bits - 1; i >= 0; i--) {
if ((x >> i & 1) == 0) continue;
if (b[i] == 0) { b[i] = x; rank++; return true; }
x ^= b[i];
}
return false;
}
boolean canMake(long x) {
for (int i = bits - 1; i >= 0; i--) if ((x >> i & 1) == 1 && b[i] != 0) x ^= b[i];
return x == 0;
}
long maxXor() {
long res = 0;
for (int i = bits - 1; i >= 0; i--) if ((res ^ b[i]) > res) res ^= b[i];
return res;
}
long count() { return 1L << rank; }
long kthSmallest(long k) { // 0-indexed; k = 0 gives 0
if (k >= count()) return -1;
long[] r = b.clone();
for (int i = 0; i < bits; i++)
if (r[i] != 0)
for (int j = i + 1; j < bits; j++) if ((r[j] >> i & 1) == 1) r[j] ^= r[i];
long res = 0;
int t = 0;
for (int i = 0; i < bits; i++) {
if (r[i] == 0) continue;
if ((k >> t & 1) == 1) res ^= r[i];
t++;
}
return res;
}
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
double[] x = new double[3];
check(gauss(new double[][]{{2, 1, -1}, {-3, -1, 2}, {-2, 1, 2}}, new double[]{8, -11, -3}, x) == UNIQUE, "unique");
check(Math.abs(x[0] - 2) < 1e-9 && Math.abs(x[1] - 3) < 1e-9 && Math.abs(x[2] + 1) < 1e-9, "x");
double[] x2 = new double[2];
check(gauss(new double[][]{{1, 1}, {2, 2}}, new double[]{3, 7}, x2) == NONE, "none");
check(gauss(new double[][]{{1, 1}, {2, 2}}, new double[]{3, 6}, x2) == INFINITE && x2[0] == 3 && x2[1] == 0, "inf");
check(Math.abs(determinant(new double[][]{{2, 1, -1}, {-3, -1, 2}, {-2, 1, 2}}) + 1) < 1e-9, "det");
long[] xm = new long[2];
gaussMod(new long[][]{{1, 2}, {3, 4}}, new long[]{3, 5}, 7, xm);
check(xm[0] == 6 && xm[1] == 2, "mod 7");
long P = 1_000_000_007L;
check(countSpanningTrees(4, new int[][]{{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}}, P) == 8, "kite");
List<int[]> k5 = new ArrayList<>();
for (int i = 0; i < 5; i++) for (int j = i + 1; j < 5; j++) k5.add(new int[]{i, j});
check(countSpanningTrees(5, k5.toArray(new int[0][]), P) == 125, "K5");
XorBasis xb = new XorBasis(4);
boolean[] ins = new boolean[5];
long[] vals = {12, 9, 7, 5, 14};
for (int i = 0; i < 5; i++) ins[i] = xb.insert(vals[i]);
check(Arrays.equals(ins, new boolean[]{true, true, true, false, false}), "insert");
check(xb.maxXor() == 14 && xb.count() == 8, "max/count");
long[] want = {0, 2, 5, 7, 9, 11, 12, 14};
for (int k = 0; k < 8; k++) check(xb.kthSmallest(k) == want[k], "kth");
Random rng = new Random(1);
for (int it = 0; it < 300; it++) {
int n = 1 + rng.nextInt(4);
double[][] a = new double[n][n];
long[][] al = new long[n][n];
double[] b = new double[n];
long[] bl = new long[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { al[i][j] = rng.nextInt(11) - 5; a[i][j] = al[i][j]; }
bl[i] = rng.nextInt(11) - 5; b[i] = bl[i];
}
double[] xs = new double[n];
if (gauss(a, b, xs) != NONE)
for (int i = 0; i < n; i++) {
double s = 0;
for (int j = 0; j < n; j++) s += a[i][j] * xs[j];
check(Math.abs(s - b[i]) < 1e-6, "a·x = b");
}
int p = 5, total = 1, count = 0;
for (int i = 0; i < n; i++) total *= p;
long[] xp = new long[n];
int[] res = gaussMod(al, bl, p, xp);
boolean found = false;
for (int code = 0; code < total; code++) {
long[] v = new long[n];
for (int i = 0, c = code; i < n; i++, c /= p) v[i] = c % p;
boolean ok = true;
for (int i = 0; i < n && ok; i++) {
long s = 0;
for (int j = 0; j < n; j++) s += al[i][j] * v[j];
ok = mod(s, p) == mod(bl[i], p);
}
if (ok) { count++; if (Arrays.equals(v, xp)) found = true; }
}
int expected = res[0] == NONE ? 0 : (int) Math.pow(p, n - res[1]);
check(count == expected && (res[0] == NONE || found), "mod brute force");
check((detMod(al, p) == 0) == (res[1] < n), "det vs rank");
}
for (int it = 0; it < 300; it++) {
int len = 1 + rng.nextInt(7);
long[] v = new long[len];
XorBasis basis = new XorBasis(6);
for (int i = 0; i < len; i++) { v[i] = rng.nextInt(64); basis.insert(v[i]); }
TreeSet<Long> all = new TreeSet<>();
for (int mask = 0; mask < (1 << len); mask++) {
long acc = 0;
for (int i = 0; i < len; i++) if ((mask >> i & 1) == 1) acc ^= v[i];
all.add(acc);
}
check(basis.count() == all.size() && basis.maxXor() == all.last(), "xor count/max");
int k = 0;
for (long s : all) check(basis.kthSmallest(k++) == s, "xor kth");
for (long q = 0; q < 64; q++) check(basis.canMake(q) == all.contains(q), "canMake");
}
System.out.println("all linear-algebra tests passed");
}
}
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <vector>
using namespace std;
const double EPS = 1e-9;
enum Status { NONE = 0, UNIQUE = 1, INFINITE = 2 };
// ---------- 1. Gaussian elimination over doubles, partial pivoting ----------
// Solves a·x = b. Fills x with one solution (free variables = 0) and returns the status.
Status gauss(vector<vector<double>> a, const vector<double>& b, vector<double>& x) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; i++) a[i].push_back(b[i]); // augmented matrix
vector<int> where(m, -1);
int row = 0;
for (int col = 0; col < m && row < n; col++) {
int piv = row;
for (int r = row + 1; r < n; r++)
if (fabs(a[r][col]) > fabs(a[piv][col])) piv = r; // partial pivoting
if (fabs(a[piv][col]) < EPS) continue; // free variable
swap(a[row], a[piv]);
where[col] = row;
for (int r = 0; r < n; r++) {
if (r == row) continue;
double f = a[r][col] / a[row][col];
if (f == 0.0) continue;
for (int c = col; c <= m; c++) a[r][c] -= f * a[row][c];
}
row++;
}
x.assign(m, 0.0);
for (int col = 0; col < m; col++)
if (where[col] != -1) x[col] = a[where[col]][m] / a[where[col]][col];
for (int r = 0; r < n; r++) {
double s = 0;
for (int c = 0; c < m; c++) s += a[r][c] * x[c];
if (fabs(s - a[r][m]) > EPS) return NONE;
}
for (int col = 0; col < m; col++) if (where[col] == -1) return INFINITE;
return UNIQUE;
}
double determinant(vector<vector<double>> a) {
int n = a.size();
double det = 1;
for (int col = 0; col < n; col++) {
int piv = col;
for (int r = col + 1; r < n; r++)
if (fabs(a[r][col]) > fabs(a[piv][col])) piv = r;
if (fabs(a[piv][col]) < EPS) return 0;
if (piv != col) { swap(a[col], a[piv]); det = -det; }
det *= a[col][col];
for (int r = col + 1; r < n; r++) {
double f = a[r][col] / a[col][col];
for (int c = col; c < n; c++) a[r][c] -= f * a[col][c];
}
}
return det;
}
// ---------- 2. Exact elimination modulo a prime p ----------
int64_t power(int64_t b, int64_t e, int64_t p) {
int64_t r = 1;
b %= p;
for (; e > 0; e >>= 1, b = b * b % p) if (e & 1) r = r * b % p;
return r;
}
int64_t md(int64_t v, int64_t p) { return ((v % p) + p) % p; }
struct ModResult { Status status; vector<int64_t> x; int rank; };
ModResult gaussMod(vector<vector<int64_t>> a, const vector<int64_t>& b, int64_t p) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; i++) {
for (auto& v : a[i]) v = md(v, p);
a[i].push_back(md(b[i], p));
}
vector<int> where(m, -1);
int row = 0;
for (int col = 0; col < m && row < n; col++) {
int piv = -1;
for (int r = row; r < n; r++) if (a[r][col] != 0) { piv = r; break; }
if (piv == -1) continue;
swap(a[row], a[piv]);
where[col] = row;
int64_t inv = power(a[row][col], p - 2, p);
for (auto& v : a[row]) v = v * inv % p;
for (int r = 0; r < n; r++) {
if (r == row || a[r][col] == 0) continue;
int64_t f = a[r][col];
for (int c = 0; c <= m; c++) a[r][c] = md(a[r][c] - f * a[row][c], p);
}
row++;
}
for (int r = row; r < n; r++) if (a[r][m] != 0) return {NONE, {}, row};
vector<int64_t> x(m, 0);
for (int col = 0; col < m; col++) if (where[col] != -1) x[col] = a[where[col]][m];
return {row < m ? INFINITE : UNIQUE, x, row};
}
int64_t detMod(vector<vector<int64_t>> a, int64_t p) {
int n = a.size();
for (auto& r : a) for (auto& v : r) v = md(v, p);
int64_t det = 1;
for (int col = 0; col < n; col++) {
int piv = -1;
for (int r = col; r < n; r++) if (a[r][col] != 0) { piv = r; break; }
if (piv == -1) return 0;
if (piv != col) { swap(a[col], a[piv]); det = p - det; }
det = det * a[col][col] % p;
int64_t inv = power(a[col][col], p - 2, p);
for (int r = col + 1; r < n; r++) {
int64_t f = a[r][col] * inv % p;
if (f == 0) continue;
for (int c = col; c < n; c++) a[r][c] = md(a[r][c] - f * a[col][c], p);
}
}
return det % p;
}
int64_t countSpanningTrees(int n, const vector<pair<int, int>>& edges, int64_t p) {
if (n == 1) return 1;
vector<vector<int64_t>> L(n, vector<int64_t>(n, 0));
for (auto [u, v] : edges) { L[u][u]++; L[v][v]++; L[u][v]--; L[v][u]--; }
vector<vector<int64_t>> minor(n - 1, vector<int64_t>(n - 1));
for (int i = 1; i < n; i++) for (int j = 1; j < n; j++) minor[i - 1][j - 1] = L[i][j];
return detMod(minor, p);
}
// ---------- 3. XOR basis (linear basis over GF(2)) ----------
struct XorBasis {
int bits, rank = 0;
vector<uint64_t> b;
explicit XorBasis(int bits) : bits(bits), b(bits, 0) {}
bool insert(uint64_t x) {
for (int i = bits - 1; i >= 0; i--) {
if (!(x >> i & 1)) continue;
if (!b[i]) { b[i] = x; rank++; return true; }
x ^= b[i];
}
return false;
}
bool canMake(uint64_t x) const {
for (int i = bits - 1; i >= 0; i--) if ((x >> i & 1) && b[i]) x ^= b[i];
return x == 0;
}
uint64_t maxXor() const {
uint64_t res = 0;
for (int i = bits - 1; i >= 0; i--) res = max(res, res ^ b[i]);
return res;
}
uint64_t count() const { return 1ULL << rank; }
// 0-indexed k-th smallest distinct subset XOR (k = 0 gives 0); returns UINT64_MAX if k too big
uint64_t kthSmallest(uint64_t k) const {
if (k >= count()) return UINT64_MAX;
vector<uint64_t> r = b;
for (int i = 0; i < bits; i++)
if (r[i])
for (int j = i + 1; j < bits; j++) if (r[j] >> i & 1) r[j] ^= r[i];
uint64_t res = 0;
int t = 0;
for (int i = 0; i < bits; i++) {
if (!r[i]) continue;
if (k >> t & 1) res ^= r[i];
t++;
}
return res;
}
};
int main() {
vector<double> x;
assert(gauss({{2, 1, -1}, {-3, -1, 2}, {-2, 1, 2}}, {8, -11, -3}, x) == UNIQUE);
assert(fabs(x[0] - 2) < 1e-9 && fabs(x[1] - 3) < 1e-9 && fabs(x[2] + 1) < 1e-9);
assert(gauss({{1, 1}, {2, 2}}, {3, 7}, x) == NONE);
assert(gauss({{1, 1}, {2, 2}}, {3, 6}, x) == INFINITE && x[0] == 3 && x[1] == 0);
assert(fabs(determinant({{2, 1, -1}, {-3, -1, 2}, {-2, 1, 2}}) + 1) < 1e-9);
auto mr = gaussMod({{1, 2}, {3, 4}}, {3, 5}, 7);
assert(mr.x[0] == 6 && mr.x[1] == 2);
const int64_t P = 1'000'000'007;
assert(countSpanningTrees(4, {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}}, P) == 8);
vector<pair<int, int>> k5;
for (int i = 0; i < 5; i++) for (int j = i + 1; j < 5; j++) k5.push_back({i, j});
assert(countSpanningTrees(5, k5, P) == 125);
XorBasis xb(4);
vector<bool> ins;
for (uint64_t v : {12, 9, 7, 5, 14}) ins.push_back(xb.insert(v));
assert((ins == vector<bool>{true, true, true, false, false}));
assert(xb.maxXor() == 14 && xb.count() == 8);
vector<uint64_t> want = {0, 2, 5, 7, 9, 11, 12, 14};
for (int k = 0; k < 8; k++) assert(xb.kthSmallest(k) == want[k]);
mt19937 rng(1);
for (int it = 0; it < 300; it++) {
int n = 1 + rng() % 4;
vector<vector<double>> a(n, vector<double>(n));
vector<vector<int64_t>> al(n, vector<int64_t>(n));
vector<double> b(n);
vector<int64_t> bl(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { al[i][j] = int64_t(rng() % 11) - 5; a[i][j] = al[i][j]; }
bl[i] = int64_t(rng() % 11) - 5; b[i] = bl[i];
}
vector<double> xs;
if (gauss(a, b, xs) != NONE)
for (int i = 0; i < n; i++) {
double s = 0;
for (int j = 0; j < n; j++) s += a[i][j] * xs[j];
assert(fabs(s - b[i]) < 1e-6);
}
const int p = 5;
int total = 1, cnt = 0;
for (int i = 0; i < n; i++) total *= p;
auto res = gaussMod(al, bl, p);
bool found = false;
for (int code = 0; code < total; code++) {
vector<int64_t> v(n);
for (int i = 0, c = code; i < n; i++, c /= p) v[i] = c % p;
bool ok = true;
for (int i = 0; i < n && ok; i++) {
int64_t s = 0;
for (int j = 0; j < n; j++) s += al[i][j] * v[j];
ok = md(s, p) == md(bl[i], p);
}
if (ok) { cnt++; if (v == res.x) found = true; }
}
int expected = res.status == NONE ? 0 : (int)lround(pow(p, n - res.rank));
assert(cnt == expected && (res.status == NONE || found));
assert((detMod(al, p) == 0) == (res.rank < n));
}
for (int it = 0; it < 300; it++) {
int len = 1 + rng() % 7;
vector<uint64_t> v(len);
XorBasis basis(6);
for (auto& e : v) { e = rng() % 64; basis.insert(e); }
set<uint64_t> all;
for (int mask = 0; mask < (1 << len); mask++) {
uint64_t acc = 0;
for (int i = 0; i < len; i++) if (mask >> i & 1) acc ^= v[i];
all.insert(acc);
}
assert(basis.count() == all.size() && basis.maxXor() == *all.rbegin());
uint64_t k = 0;
for (uint64_t s : all) assert(basis.kthSmallest(k++) == s);
for (uint64_t q = 0; q < 64; q++) assert(basis.canMake(q) == (all.count(q) > 0));
}
cout << "all linear-algebra tests passed\n";
}
const EPS = 1e-9;
const NONE = 0, UNIQUE = 1, INFINITE = 2;
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("check failed: " + what);
}
// ---------- 1. Gaussian elimination over doubles, partial pivoting ----------
/** Solves a·x = b. Returns the status and one solution (free variables = 0). */
function gauss(a: number[][], b: number[]): { status: number; x: number[] } {
const n = a.length, m = a[0].length;
const M = a.map((row, i) => [...row, b[i]]);
const where: number[] = new Array(m).fill(-1);
let row = 0;
for (let col = 0; col < m && row < n; col++) {
let piv = row;
for (let r = row + 1; r < n; r++) if (Math.abs(M[r][col]) > Math.abs(M[piv][col])) piv = r;
if (Math.abs(M[piv][col]) < EPS) continue; // free variable
[M[row], M[piv]] = [M[piv], M[row]];
where[col] = row;
for (let r = 0; r < n; r++) {
if (r === row) continue;
const f = M[r][col] / M[row][col];
if (f === 0) continue;
for (let c = col; c <= m; c++) M[r][c] -= f * M[row][c];
}
row++;
}
const x: number[] = new Array(m).fill(0);
for (let col = 0; col < m; col++) if (where[col] !== -1) x[col] = M[where[col]][m] / M[where[col]][col];
for (let r = 0; r < n; r++) {
let s = 0;
for (let c = 0; c < m; c++) s += M[r][c] * x[c];
if (Math.abs(s - M[r][m]) > EPS) return { status: NONE, x: [] };
}
return { status: where.includes(-1) ? INFINITE : UNIQUE, x };
}
function determinant(a: number[][]): number {
const n = a.length;
const M = a.map((r) => [...r]);
let det = 1;
for (let col = 0; col < n; col++) {
let piv = col;
for (let r = col + 1; r < n; r++) if (Math.abs(M[r][col]) > Math.abs(M[piv][col])) piv = r;
if (Math.abs(M[piv][col]) < EPS) return 0;
if (piv !== col) { [M[col], M[piv]] = [M[piv], M[col]]; det = -det; }
det *= M[col][col];
for (let r = col + 1; r < n; r++) {
const f = M[r][col] / M[col][col];
for (let c = col; c < n; c++) M[r][c] -= f * M[col][c];
}
}
return det;
}
// ---------- 2. Exact elimination modulo a prime p ----------
// Residues are below 2^30, so a product needs up to 60 bits: more than a double holds exactly.
// mulMod splits b into 15-bit halves so every intermediate stays below 2^53.
function mulMod(a: number, b: number, p: number): number {
const hi = Math.floor(b / 32768), lo = b % 32768;
return (((a * hi) % p) * 32768 + a * lo) % p;
}
function powMod(b: number, e: number, p: number): number {
let r = 1;
b %= p;
for (; e > 0; e = Math.floor(e / 2)) {
if (e % 2 === 1) r = mulMod(r, b, p);
b = mulMod(b, b, p);
}
return r;
}
const md = (v: number, p: number): number => ((v % p) + p) % p;
function gaussMod(a: number[][], b: number[], p: number): { status: number; x: number[]; rank: number } {
const n = a.length, m = a[0].length;
const M = a.map((row, i) => [...row.map((v) => md(v, p)), md(b[i], p)]);
const where: number[] = new Array(m).fill(-1);
let row = 0;
for (let col = 0; col < m && row < n; col++) {
let piv = -1;
for (let r = row; r < n; r++) if (M[r][col] !== 0) { piv = r; break; }
if (piv === -1) continue;
[M[row], M[piv]] = [M[piv], M[row]];
where[col] = row;
const inv = powMod(M[row][col], p - 2, p);
M[row] = M[row].map((v) => mulMod(v, inv, p));
for (let r = 0; r < n; r++) {
if (r === row || M[r][col] === 0) continue;
const f = M[r][col];
for (let c = 0; c <= m; c++) M[r][c] = md(M[r][c] - mulMod(f, M[row][c], p), p);
}
row++;
}
for (let r = row; r < n; r++) if (M[r][m] !== 0) return { status: NONE, x: [], rank: row };
const x: number[] = new Array(m).fill(0);
for (let col = 0; col < m; col++) if (where[col] !== -1) x[col] = M[where[col]][m];
return { status: row < m ? INFINITE : UNIQUE, x, rank: row };
}
function detMod(a: number[][], p: number): number {
const n = a.length;
const M = a.map((r) => r.map((v) => md(v, p)));
let det = 1;
for (let col = 0; col < n; col++) {
let piv = -1;
for (let r = col; r < n; r++) if (M[r][col] !== 0) { piv = r; break; }
if (piv === -1) return 0;
if (piv !== col) { [M[col], M[piv]] = [M[piv], M[col]]; det = md(-det, p); }
det = mulMod(det, M[col][col], p);
const inv = powMod(M[col][col], p - 2, p);
for (let r = col + 1; r < n; r++) {
const f = mulMod(M[r][col], inv, p);
if (f === 0) continue;
for (let c = col; c < n; c++) M[r][c] = md(M[r][c] - mulMod(f, M[col][c], p), p);
}
}
return det;
}
function countSpanningTrees(n: number, edges: [number, number][], p: number): number {
if (n === 1) return 1;
const L = Array.from({ length: n }, () => new Array(n).fill(0));
for (const [u, v] of edges) { L[u][u]++; L[v][v]++; L[u][v]--; L[v][u]--; }
return detMod(L.slice(1).map((r) => r.slice(1)), p);
}
// ---------- 3. XOR basis (linear basis over GF(2)) ----------
// JS bitwise operators work on 32-bit ints, so this version keeps values below 2^31.
// For 64-bit values use BigInt with the same code shape.
class XorBasis {
readonly bits: number;
readonly b: number[];
rank = 0;
constructor(bits: number) {
this.bits = bits;
this.b = new Array(bits).fill(0);
}
insert(x: number): boolean {
for (let i = this.bits - 1; i >= 0; i--) {
if (((x >> i) & 1) === 0) continue;
if (this.b[i] === 0) { this.b[i] = x; this.rank++; return true; }
x ^= this.b[i];
}
return false;
}
canMake(x: number): boolean {
for (let i = this.bits - 1; i >= 0; i--) if (((x >> i) & 1) === 1 && this.b[i] !== 0) x ^= this.b[i];
return x === 0;
}
maxXor(): number {
let res = 0;
for (let i = this.bits - 1; i >= 0; i--) if ((res ^ this.b[i]) > res) res ^= this.b[i];
return res;
}
count(): number {
return 2 ** this.rank;
}
kthSmallest(k: number): number { // 0-indexed; k = 0 gives 0
if (k >= this.count()) return -1;
const r = [...this.b];
for (let i = 0; i < this.bits; i++)
if (r[i] !== 0) for (let j = i + 1; j < this.bits; j++) if (((r[j] >> i) & 1) === 1) r[j] ^= r[i];
let res = 0, t = 0;
for (let i = 0; i < this.bits; i++) {
if (r[i] === 0) continue;
if (Math.floor(k / 2 ** t) % 2 === 1) res ^= r[i];
t++;
}
return res;
}
}
// ---------- demo and brute-force checks ----------
{
const r1 = gauss([[2, 1, -1], [-3, -1, 2], [-2, 1, 2]], [8, -11, -3]);
check(r1.status === UNIQUE && [2, 3, -1].every((e, i) => Math.abs(r1.x[i] - e) < 1e-9), "unique");
check(gauss([[1, 1], [2, 2]], [3, 7]).status === NONE, "none");
const r3 = gauss([[1, 1], [2, 2]], [3, 6]);
check(r3.status === INFINITE && r3.x[0] === 3 && r3.x[1] === 0, "infinite");
check(Math.abs(determinant([[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]) + 1) < 1e-9, "det");
check(gaussMod([[1, 2], [3, 4]], [3, 5], 7).x.join() === "6,2", "mod 7");
const P = 1_000_000_007;
check(countSpanningTrees(4, [[0, 1], [0, 2], [1, 2], [1, 3], [2, 3]], P) === 8, "kite");
const k5: [number, number][] = [];
for (let i = 0; i < 5; i++) for (let j = i + 1; j < 5; j++) k5.push([i, j]);
check(countSpanningTrees(5, k5, P) === 125, "K5");
const xb = new XorBasis(4);
check([12, 9, 7, 5, 14].map((v) => xb.insert(v)).join() === "true,true,true,false,false", "insert");
check(xb.maxXor() === 14 && xb.count() === 8, "max/count");
check([0, 1, 2, 3, 4, 5, 6, 7].map((k) => xb.kthSmallest(k)).join() === "0,2,5,7,9,11,12,14", "kth");
let seed = 1;
const rand = (k: number): number => { seed = (seed * 48271) % 2147483647; return seed % k; };
for (let it = 0; it < 300; it++) {
const n = 1 + rand(4);
const a = Array.from({ length: n }, () => Array.from({ length: n }, () => rand(11) - 5));
const b = Array.from({ length: n }, () => rand(11) - 5);
const g = gauss(a, b);
if (g.status !== NONE)
for (let i = 0; i < n; i++) check(Math.abs(a[i].reduce((s, v, j) => s + v * g.x[j], 0) - b[i]) < 1e-6, "a·x=b");
const p = 5;
const res = gaussMod(a, b, p);
let cnt = 0, found = false;
for (let code = 0; code < p ** n; code++) {
const v: number[] = [];
for (let i = 0, c = code; i < n; i++, c = Math.floor(c / p)) v.push(c % p);
const ok = a.every((row, i) => md(row.reduce((s, coef, j) => s + coef * v[j], 0), p) === md(b[i], p));
if (ok) { cnt++; if (v.join() === res.x.join()) found = true; }
}
check(cnt === (res.status === NONE ? 0 : p ** (n - res.rank)) && (res.status === NONE || found), "mod brute");
check((detMod(a, p) === 0) === (res.rank < n), "det vs rank");
}
for (let it = 0; it < 300; it++) {
const len = 1 + rand(7);
const v = Array.from({ length: len }, () => rand(64));
const basis = new XorBasis(6);
v.forEach((e) => basis.insert(e));
const all = new Set<number>();
for (let mask = 0; mask < 1 << len; mask++) {
let acc = 0;
for (let i = 0; i < len; i++) if ((mask >> i) & 1) acc ^= v[i];
all.add(acc);
}
const sorted = [...all].sort((x, y) => x - y);
check(basis.count() === sorted.length && basis.maxXor() === sorted[sorted.length - 1], "xor count/max");
sorted.forEach((s, k) => check(basis.kthSmallest(k) === s, "xor kth"));
for (let q = 0; q < 64; q++) check(basis.canMake(q) === all.has(q), "canMake");
}
console.log("all linear-algebra tests passed");
}
Real-world uses
- Numerical libraries. LAPACK's
dgetrf/dgesv(LU with partial pivoting) is the engine behindnumpy.linalg.solve, MATLAB's backslash operator for square dense systems, R'ssolve, and Julia's\. They implement exactly the algorithm above, blocked for cache efficiency (Anderson et al., LAPACK Users' Guide, 3rd ed., SIAM 1999). - Circuit simulation. SPICE builds one linear equation per circuit node (Kirchhoff's current law, modified nodal analysis) and solves the resulting sparse system with LU at every time step and every Newton iteration (Nagel, "SPICE2: A Computer Program to Simulate Semiconductor Circuits", UC Berkeley, 1975).
- Search ranking. PageRank is an eigenvector computation (above); recommendation systems factorise rating matrices with least squares (alternating least squares in Apache Spark MLlib).
- Graphics and games. Every vertex shader multiplies by 4×4 matrices; physics engines solve linear complementarity problems with Gauss–Seidel-style iterations; inverse kinematics uses least squares on Jacobian matrices.
- Error-correcting codes and cryptography. Linear codes (Hamming, Reed–Solomon, the LDPC codes in Wi-Fi and 5G) encode with a generator matrix and decode by solving linear systems over finite fields. Reed–Solomon works over GF() — the scheme used in QR codes and RAID-6. Linear algebra over GF(2) is also how the linear and algebraic attacks on stream ciphers work, and the final step of factoring algorithms like the quadratic sieve and the number field sieve is finding a dependency in a huge sparse GF(2) matrix (block Lanczos / Wiedemann).
- Network analysis. The matrix-tree theorem and Laplacian eigenvalues measure network reliability and connectivity (algebraic connectivity, Fiedler 1973); spectral clustering uses Laplacian eigenvectors.
- Statistics and machine learning. Linear regression is least squares; ridge regression solves ; Gaussian processes solve systems with covariance matrices (via Cholesky, the symmetric cousin of LU).
Pitfalls & edge cases
- Forgetting to pivot with doubles. The example above returns instead of 1. Always pick the largest pivot.
- An absolute EPS on badly scaled data. With
EPS = 1e-9, the system , is reported as having infinitely many solutions with — run on the code above, it does exactly that. Either rescale rows so their largest entry is about 1, or compare againstEPS * (largest |entry| in the matrix). - Ill-conditioned matrices. The Hilbert matrix is the classic trap. Solving (true answer: all ones) with the double code above gives a maximum error of for and for ; for a pivot falls below EPS and the code wrongly reports "infinitely many" solutions, with an error of 28. Pivoting cannot fix a problem that is itself ill-conditioned. If the answer must be exact, use fractions or mod .
- Comparing doubles with
== 0. After elimination, "zero" entries are often , not 0. Use the tolerance consistently, including in the final consistency check. - Elimination mod a composite number. Inverses may not exist. Use a prime, a gcd-style elimination, or CRT.
- Overflow mod . With ,
a * bneeds 64 bits;f * M[row][c]in Java/C++ must belong/int64_t. In JavaScript a product of two residues can exceed and silently lose digits: the TypeScript code splits one factor into 15-bit halves. - Negative values mod . In C++, Java and JavaScript,
-3 % 7is-3. Normalise with((v % p) + p) % p. - Using the determinant to decide singularity in floating point. , yet the matrix is perfectly well-conditioned. Use the rank (number of pivots above tolerance) or the condition number, not "det is tiny".
- XOR basis: wrong bit width. Values up to need 60 bits; using 31 (or JavaScript's 32-bit
^on large numbers) silently drops high bits. Uselong/uint64_t, Python ints, orBigInt. - XOR basis: -th smallest without reducing. The unreduced basis does not map the bits of to sorted order. With
b = {1100, 0101, 0010}, selecting the top vector alone gives 12, but the 5th smallest (index 4) is 9. - XOR basis: empty subset. Decide whether 0 (the empty XOR) counts, and correct counts and by one if it must be non-empty and every element was independent.
- Expected values with an unreachable goal. Singular matrix; check reachability first.
- Matrix-tree theorem on a disconnected graph. It correctly returns 0 — but if you expected a spanning forest count, that is a different question (multiply the counts of each component).
Variations
- LU, Cholesky, QR. LU records elimination as (with the row permutation from pivoting) so that each new right side costs . Cholesky () is LU for symmetric positive-definite matrices, half the work and no pivoting needed. QR ( with orthogonal ) is the stable route to least squares.
- Bareiss's fraction-free elimination. Computes integer determinants exactly using only integer division that is guaranteed to be exact, keeping intermediate numbers bounded by the size of minors (Bareiss, Mathematics of Computation, 1968).
- Gaussian elimination over GF(2) with bitsets.
std::bitset<N>rows, XOR whole rows at once: the standard way to solve "lights out" style puzzles and Codeforces problems with thousands of GF(2) equations. - Prefix linear bases. Keep, for every prefix of an array, a basis that prefers the most recent vectors (store the index along with each vector and swap in newer ones during insertion). Then "max XOR of a subset of
a[l..r]" is answered from prefix using only vectors with index (Codeforces 1100F). - Linear basis over other fields. The same insert/reduce idea works mod any prime for vectors of residues.
- Eigenvalues and eigenvectors. Power iteration finds the dominant eigenvector; the QR algorithm finds all eigenvalues of a dense matrix in . Characteristic polynomials of small integer matrices can be computed mod by reduction to Hessenberg form.
- Berlekamp–Massey. Finds the shortest linear recurrence for a sequence; it is Gaussian elimination specialised to Hankel matrices, instead of (see Matrix Exponentiation).
- Linear programming. The simplex method is a sequence of Gauss–Jordan pivots chosen to improve an objective. Linear Programming covers it.
- Polynomial interpolation. Finding the degree- polynomial through points is a linear (Vandermonde) system; Lagrange interpolation solves it in without elimination, and FFT-based methods in (FFT & NTT).
Practice ladder
Easy to hard. Problems are described in my own words; follow the links for the full statements. The key solutions below were run against brute force on small inputs.
1. Find XOR Sum of All Pairs Bitwise AND (LeetCode 1835) — XOR together a[i] & b[j] over all pairs. Teaches that AND distributes over XOR — GF(2) multiplication distributes over GF(2) addition — so the answer is (xor of a) & (xor of b).
Hint
Bit by bit, the pair contributes 1 iff both bits are 1; the count of such pairs is (ones in ) × (ones in ), and its parity is the product of the parities.
2. Xor Sum 3 (AtCoder ABC 141 F) — Paint some of the numbers red and the rest blue (each colour used at least once) to maximise (XOR of the reds) + (XOR of the blues). Teaches a basis on a masked problem.
Solution
Let be the XOR of everything; group 2's XOR is where is group 1's. Bits set in contribute exactly once whatever you do. For bits not set in , both groups have the same bit, so it counts twice: maximise restricted to the bits outside . Clear the bits from every number, build a basis, take its maximum ; the answer is .
def xor_sum3(a):
t = 0
for v in a:
t ^= v
mask = ~t & ((1 << 60) - 1)
basis = [0] * 60
for v in a:
v &= mask
for i in reversed(range(60)):
if not v >> i & 1:
continue
if not basis[i]:
basis[i] = v
break
v ^= basis[i]
best = 0
for i in reversed(range(60)):
best = max(best, best ^ basis[i])
return t + 2 * best
assert xor_sum3([3, 6, 5]) == 12
assert xor_sum3([23, 36, 66, 65]) == 188
3. (Zero XOR Subset)-less (Codeforces 1101G) — Cut an array into the maximum number of segments so that no non-empty set of segments has XOR 0. Teaches "rank of the prefix XORs".
Hint
Segment XORs are differences of prefix XORs, so any set of segments' XOR is an XOR of some prefix values. The answer is the rank of the prefix XORs — or if the total XOR is 0.
4. Square Subsets (Codeforces 895C) — Count non-empty subsets whose product is a perfect square; values are at most 70. Teaches parity vectors over GF(2).
Solution
Each value maps to a 19-bit vector: bit is the parity of the exponent of the -th prime . A product is a square iff the XOR of the vectors is 0. The number of subsets with XOR 0 is ; subtract 1 for the empty subset.
def square_subsets(a, mod=10**9 + 7):
primes = [p for p in range(2, 71) if all(p % d for d in range(2, p))]
basis = [0] * len(primes)
rank = 0
for v in a:
vec = 0
for j, p in enumerate(primes):
while v % p == 0:
v //= p
vec ^= 1 << j
for i in reversed(range(len(primes))):
if not vec >> i & 1:
continue
if not basis[i]:
basis[i] = vec
rank += 1
break
vec ^= basis[i]
return (pow(2, len(a) - rank, mod) - 1) % mod
assert square_subsets([1, 1, 1, 1]) == 15
assert square_subsets([2, 2, 2, 2]) == 7
assert square_subsets([1, 2, 4, 5, 8]) == 7
5. Mahmoud and Ehab and yet another xor task (Codeforces 959F) — Queries ask: how many subsequences of the first elements have XOR ? Teaches the count with incremental bases.
Hint
Process queries sorted by while inserting elements. Answer: if reduces to 0, else 0.
6. Shortest Path Problem? (Codeforces 845G) — Minimum XOR-weight path from 1 to in an undirected graph (walks may repeat edges). Teaches the cycle basis.
Solution
DFS from vertex 1 assigning d[v] = XOR of the tree path. Each non-tree edge gives a cycle value d[u] ^ d[v] ^ w; insert it into a basis. Any walk's XOR is d[n] XOR some combination of cycle values (go around a cycle and come back: the connecting path cancels). Minimise d[n] by greedily XOR-ing basis vectors from the top bit when it makes the value smaller.
def min_xor_path(n, edges):
adj = [[] for _ in range(n + 1)]
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w))
d = [-1] * (n + 1)
d[1] = 0
basis = [0] * 31
stack = [1]
def insert(x):
for i in reversed(range(31)):
if x >> i & 1:
if not basis[i]:
basis[i] = x
return
x ^= basis[i]
while stack:
u = stack.pop()
for v, w in adj[u]:
if d[v] == -1:
d[v] = d[u] ^ w
stack.append(v)
else:
insert(d[u] ^ d[v] ^ w) # tree edges give 0, which is harmless
res = d[n]
for i in reversed(range(31)):
res = min(res, res ^ basis[i])
return res
assert min_xor_path(3, [(1, 2, 3), (1, 3, 2), (3, 2, 0)]) == 2
assert min_xor_path(2, [(1, 1, 3), (1, 2, 3)]) == 0
7. Ivan and Burgers (Codeforces 1100F) — Many range queries: maximum XOR of a subset of c[l..r]. Teaches the prefix linear basis that prefers recent elements.
Hint
Sweep left to right. Keep b[i] and pos[i]; when inserting , if pos[i] < r at an occupied bit, swap the newer vector into the slot and keep reducing the older one. For a query , use only slots with pos[i] >= l.
8. Broken robot (Codeforces 24D) — A robot on an board moves randomly (stay, left, right, down) until it reaches the bottom row; find the expected number of steps. Teaches expected-value equations with cycles inside a row, solved in per row because the system is tridiagonal.
Hint
Rows are processed bottom-up (moving down is acyclic), but within a row, cells depend on their left and right neighbours. Each row is a tridiagonal system: eliminate left to right, substitute back right to left. Handle separately.
9. Museum (Codeforces 113D) — Two people walk randomly in a small museum graph until they meet in a room; for each room, find the probability they meet there. Teaches building a system over pairs of states ( unknowns) and solving it with doubles.
Hint
Unknown = expected number of times the pair is in state before meeting. Each state's equation sums transitions from all non-meeting pair states. The probability of meeting in room is .
10. Vasya and Shifts (Codeforces 832E) — Strings over the letters a–e act as vectors mod 5; each given string may be applied 0 to 4 times, and each query asks in how many ways a target string can be produced. Teaches elimination mod 5 and the count .
Hint
Eliminate the string-vectors once (as columns), recording the transforms; for each query, check consistency and answer or 0.
11. Two Sets (Codeforces 251D) — Split numbers into two sets to maximise (XOR of set 1) + (XOR of set 2), breaking ties by making set 1's XOR as small as possible. Teaches GF(2) systems with thousands of unknowns, bitset rows, and adding equations greedily, bit by bit.
Hint
Unknown = 1 if number goes to set 1. Process bits by priority (bits where the total XOR is 0 first, then the others), each time trying to add the equation "this bit of set 1's XOR is 1" (or 0) and keeping it only if the system stays consistent. Use bitset<100000> rows.
12. Highways (SPOJ HIGH) — Count the ways to build a network of highways connecting all cities, given the allowed city pairs. Teaches Kirchhoff's theorem directly.
Hint
Exactly count_spanning_trees — but the exact count is wanted, not a residue. Use Bareiss's fraction-free elimination, or long doubles and round, or compute mod a few primes and combine.
Common mistakes & interview follow-ups
"Why do we pivot?" To avoid dividing by small numbers, which turns rounding errors of into errors of order 1. With exact arithmetic it is only needed to avoid a zero pivot.
"How do you know if the system has no solution?" After elimination a row reads . Equivalently .
"What is the cost, and can you do better?" . Sparse, banded or GF(2) structure helps ( iterations, tridiagonal, bitsets). Asymptotically via fast matrix multiplication, never in practice.
"Max XOR of two numbers vs max XOR of a subset?" Two numbers: a binary trie, (Bit Manipulation). Any subset: an XOR basis, . Different tools: a basis cannot tell you about pairs, a trie cannot tell you about subsets.
"Why is the number of distinct subset XORs a power of two?" It is the size of a vector space over GF(2), which is .
"Expected steps with cycles — why not DP?" No topological order. Each state's equation refers to states not yet computed; solve them simultaneously.
"Do you ever need the inverse?" Rarely. Solve with LU; it is faster and more accurate than forming and multiplying.
Mistakes interviewers watch for: an EPS that is absolute on scaled data; forgetting the sign flip of the determinant on swaps; elimination mod a non-prime; reading the answer from a free column; the -th smallest XOR without reducing the basis; forgetting that the empty subset gives 0.
Quick quiz
1. In the trace, why was row 2 (not row 1) used as the first pivot?
Answer
Partial pivoting picks the largest absolute value in the column: and .
2. A 4×6 system (4 equations, 6 unknowns) has rank 4 and is consistent. How many free variables? How many solutions mod 7?
Answer
free variables; solutions mod 7.
3. Forward elimination on a 3×3 matrix used one row swap and found pivots 2, −1, 5. What is the determinant?
Answer
.
4. You insert 6, 10, 12 into an XOR basis. What is the rank, the maximum subset XOR, and the number of distinct subset XORs?
Answer
6 = 0110, 10 = 1010, 12 = 1100 = 6 ⊕ 10. Rank 2, so 4 distinct values: 0, 6, 10, 12. Maximum 12.
5. How many spanning trees does the cycle graph have?
Answer
5: remove any one of the 5 edges. (Kirchhoff agrees: the reduced Laplacian of has determinant .)
6. Why does the mod- code not look for the largest pivot?
Answer
Arithmetic mod is exact; any nonzero pivot gives exactly the same final answer. "Largest" is meaningless and pointless mod .
Further reading / sources
- Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM 1997 — Lectures 20–23 (Gaussian elimination, pivoting, stability).
- Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley–Cambridge Press 2016 — Chapters 2 and 5 (elimination, determinants).
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 28 (LUP decomposition, inverses, least squares).
- Joseph F. Grcar, "Mathematicians of Gaussian Elimination", Notices of the AMS 58(6), 2011 — the history from the Nine Chapters to Gauss and von Neumann.
- cp-algorithms: Gauss method for solving system of linear equations, Calculating the determinant, Kirchhoff's theorem.
- Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK — "Cayley's formula for the number of trees" (matrix-tree theorem).
- Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, "The PageRank Citation Ranking: Bringing Order to the Web", Stanford InfoLab technical report, 1999; Amy N. Langville and Carl D. Meyer, Google's PageRank and Beyond, Princeton 2006.
- Erwin H. Bareiss, "Sylvester's identity and multistep integer-preserving Gaussian elimination", Mathematics of Computation 22(103), 1968.
- E. Anderson et al., LAPACK Users' Guide, 3rd ed., SIAM 1999.
Lessons: previous — Probability & Expected Value · next — FFT & NTT · module — Math · course — DSA: Zero to Mastery.
Related Archon pages: Matrix Exponentiation · Probability DP · Bit Manipulation · SOS DP · Minimum Spanning Trees · Union-Find · Matrices & Grids · Modular Arithmetic · Search & Recommendation.