The same sum without its minus signs

The determinant is a sum over the $n!$ permutations, each term a product of one entry from each row and column, with a sign attached. Delete the signs and the definition still makes sense:

$$\operatorname{per} A = \sum_{σ} a_{σ(1)1} a_{σ(2)2} \cdots a_{σ(n)n}.$$

That is the permanent. It is the same list of products, added up differently, and the difference is worth an essay because almost nothing about the determinant survives the change.

What the unsigned sum counts #

The permanent is the better of the two at counting, and the reason is that a count has no negative terms in it.

Take a matrix of ones and zeroes — the shape an incidence question always produces. Each term of the sum is a product of $n$ entries, one from each row and column, so it is $1$ when every chosen entry is a one and $0$ otherwise. The permanent is therefore the number of ways to choose one entry per row and column, all of them ones — which is the number of perfect matchings in the bipartite graph whose edges are the ones.

That single fact is why permanents appear wherever matchings do. Whether a matching exists at all is Hall’s condition and is easy; how many there are is the permanent, and is not.

It is also where this anchor meets the Latin squares. Extending a Latin rectangle by one row means choosing, for each column, a symbol it has not used — one entry per column and per symbol, from the pattern of what is still available. The number of ways to do it is the permanent of that pattern, and the count of Latin squares is a product of such permanents, one per row.

And derangements are the permanent of the matrix with zeroes on the diagonal and ones everywhere else — the arrangements where nobody is matched to their own item.

Two objects, one list of products #

It is worth pausing on how close the two are before cataloguing how differently they behave, because the closeness is the surprising part.

Both are sums over the same $n!$ products. Both are multilinear in the rows and in the columns. Both are unchanged by transposing the matrix. Both take the value one on the identity, and both vanish on a matrix with a zero row. On a triangular matrix both are the product of the diagonal. On a matrix of ones and zeroes both are integers, and the permanent is the number of terms that survive while the determinant is that number counted with signs.

The list of shared properties is long enough that a reader might expect the two to be equally tractable, and the point of this essay is that a single missing property separates them completely. This is a pattern worth recognising: two definitions that differ in one clause can produce objects whose whole characters differ, and the clause that matters is rarely the one that looks most substantial. There, Latin squares and group tables differed by associativity alone and sixteen of five hundred and seventy-six survived it. Here the clause is a minus sign.

The property that was deleted #

Recall the three conditions that force the determinant: multilinear in the columns, zero when two columns agree, one on the identity. The permanent keeps the first and the third, and drops the second.

That looks like a small concession. It is not, because the alternating property is precisely the licence for row operations.

Adding a multiple of one column to another changes a multilinear function by a multiple of its value on a matrix with a repeated column. For the determinant that correction is zero, so the operation is free. For the permanent the correction is a permanent with a repeated column, which is a positive number, so the operation changes the answer — and the figures compute both before and after.

What else fails #

Multiplicativity. $\det(AB) = \det(A)\det(B)$ was proved in this ladder by the uniqueness theorem: the map $A \mapsto \det(AB)/\det(B)$ has all three properties, so it is the determinant. The permanent has no such uniqueness behind it, and no product rule: $\operatorname{per}(AB)$ has no useful relation to $\operatorname{per}(A)$ and $\operatorname{per}(B)$ at all.

Invariance under change of basis. The determinant of $P^{-1} A P$ is $\det A$, which is what makes it a property of a map rather than of a matrix. Without multiplicativity that argument evaporates, and the permanent genuinely depends on the coordinates: it is a function of a matrix, and it means nothing about the linear map that matrix represents.

Elimination. Reducing a matrix to triangular form is a sequence of row operations, and it is how any determinant of size worth mentioning is actually evaluated. Every one of those operations is illegal for the permanent.

The only symmetries the permanent has left are permuting rows, permuting columns, and scaling a row or column, all of which the determinant has too. Everything the determinant has beyond those came from the alternating property.

What is left to compute with #

Without elimination the naive route is the definition, with its $n!$ terms. There is one substantially better classical method: Ryser’s formula, from 1963, which rewrites the permanent by inclusion and exclusion over subsets of the columns and costs about $2^n n$ operations rather than $n!$. At $n = 20$ that is the difference between a few million million operations and a few tens of millions, and at $n = 60$ both are hopeless.

That nothing much better is known is not for want of trying, and the reason has a name: Valiant proved in 1979 that computing the permanent of a matrix of ones and zeroes is complete for a class of counting problems believed to have no efficient algorithm — the same statement, in that setting, as “counting perfect matchings is hard”. The cost of procedures belongs to a different collection than this one; what belongs here is the algebraic half of the explanation, and it is the one this essay has been making. Elimination is the use of cancellation, and the permanent has none.

The contrast is sharp enough to be worth stating as a pair of sentences. The determinant of a matrix of ones and zeroes is a signed sum with no combinatorial meaning, and it is computable in a few thousand operations at $n = 20$. The permanent of the same matrix is an exact count of something a reader can see, and nobody can compute it at $n = 60$.

Where the two numbers actually differ #

A small experiment makes the divergence concrete. On a matrix of ones and zeroes, the determinant is the number of even matchings minus the number of odd ones, and the permanent is their sum. So the two agree exactly when every matching has the same parity, and differ by twice the smaller group otherwise.

That reading gives a rough sense of when the determinant is a usable proxy. On a matrix whose ones are confined to a band near the diagonal, most matchings are close to the identity permutation and the parities are unbalanced, so the determinant is a substantial fraction of the permanent. On a dense matrix the parities are nearly balanced, cancellation is nearly total, and the determinant is a small number sitting beside an enormous one — the all-ones matrix at size $n$ has permanent $n!$ and determinant zero, which is the extreme case of the phenomenon.

Zero is the right answer for the determinant there, of course: the all-ones matrix has repeated columns. But the pairing is exact and worth seeing — every one of the $n!$ terms is $1$, exactly half the permutations are even, and the sum with signs is nothing at all while the sum without is everything.

Could the signs be put back? #

A natural hope, and one that was pursued seriously: perhaps the entries of a matrix can be given fixed signs — some entries negated, in a pattern depending only on the position — so that the determinant of the signed matrix equals the permanent of the original.

At $n = 2$ it works. Negate the entry in the bottom left, and $ad - (-b)c = ad + bc$, which is the permanent. Pólya observed this in 1913.

At $n \ge 3$ no such pattern exists, which Szegő proved in the same year. The reason is a counting one: the $n!$ terms must all end up positive, and the sign a term receives is the product of the signs of its entries times the sign of its permutation, and those constraints are inconsistent as soon as there are enough permutations to constrain each other.

There is a subtler version of the question that is not hopeless — sign the entries in a way that depends on the matrix, so that a determinant computes that particular permanent — and it turns out to be possible exactly for a describable class of patterns. That is a genuinely deep result and it is a result about which patterns, not about all of them.

Bounds instead of a value #

Since the value is out of reach, the subject deals in bounds, and the two classical ones bracket it from both sides.

Brégman’s inequality, from 1973 — the bound that also puts a ceiling on how many Latin squares there can be — bounds the permanent of a matrix of ones and zeroes above: with $r_i$ ones in row $i$, the permanent is at most $\prod_i (r_i!)^{1/r_i}$. It is sharp when the ones form disjoint blocks.

The van der Waerden bound, conjectured in 1926 and proved by Egorychev and Falikman in 1981, bounds it below for doubly stochastic matrices: at least $n!/n^n$. Sharp on the matrix with every entry $1/n$, which is the uniform mixture of all assignments.

Between them they pin the number of Latin squares of order six to within a factor of a few thousand — the truth is about four hundred times the lower bound and a ninth of the upper — which is a fair description of how well anybody can do with an object that is exactly defined and not computable.

The permanent of a doubly stochastic matrix #

One setting deserves its own section, because it is where the permanent is most studied and least like a count.

A doubly stochastic matrix has non-negative entries with every row and every column summing to one. Such a matrix is a mixture of permutations — that is Birkhoff’s theorem, and it is what a lottery over whole assignments is about — and its permanent measures something like how spread out the mixture is.

At one extreme sits a permutation matrix itself, whose permanent is one: the mixture is concentrated on a single assignment. At the other sits the matrix with every entry $1/n$, the uniform mixture, whose permanent is $n!/n^n$. The van der Waerden bound says the uniform mixture is the minimum, which is the opposite of what a first guess suggests — the most spread-out mixture has the smallest permanent, because the permanent is a sum of products and products of many small numbers are small.

That inequality was conjectured in 1926 and resisted for fifty-five years, which is a long time for a statement about $n \times n$ matrices with a single-line hypothesis. Both proofs, found independently in 1981, are analytic: they treat the permanent as a function on the polytope of doubly stochastic matrices and study where it can be smallest. Nothing combinatorial about the argument, and nothing about it suggests a way to compute the number it bounds.

What the pictures cannot show #

The figures compute both sums at $n = 3$, where the six terms fit on the page. At $n = 4$ there are twenty-four terms and the table would stop being readable; at $n = 10$ there are over three million. So every drawing here is at the size where the distinction is visible and the difficulty is not, which is an uncomfortable place to be arguing that one of the two is hard.

What the drawings can do, and do, is exhibit the mechanism: the same products listed once, added two ways, with a row operation applied to both and its effect measured. That is the entire content of the essay in a form that can be checked, and it is checked — the determinant is asserted unchanged and the permanent asserted to move, at every parameter any figure here uses.

The hardness itself has no figure and could not have one. A statement that no efficient algorithm exists is a statement about every algorithm, and a picture exhibits one thing at a time. This collection’s habit is to draw the exhaustion when the exhaustion fits and to say plainly when it does not, and here it does not: $n!$ is six at three, and past all drawing at ten.

What this anchor has come to #

Five rungs, and the determinant has been an area, a volume forced by three conditions, the covolume of a lattice, a counting device, and — by its absence — an explanation of why a very similar sum is intractable.

The thread running through all of them is the alternating property. It is what makes the two-dimensional formula have a minus sign, what reduces $n^n$ terms to $n!$, what kills the non-trees in Kirchhoff’s expansion and the crossing paths in the path lemma, and what licenses the elimination that makes the whole thing computable. Take it away and the object still exists, still counts things, and is useless to calculate with.

What is left unwritten and named: the exterior algebra, where the alternating property is built into the objects rather than imposed on a function, and the determinant becomes the statement that the top exterior power of an $n$-dimensional space is one-dimensional. That is the account under which every fact in this ladder is a corollary, and it is a subject rather than a rung.