The rank that stops being typical

A rank that is not a property of the tensor found two sentences with no analogue for matrices. The same eight real numbers can have rank three over the reals and rank two over the complexes. And a random 2 × 2 × 2 tensor with independent normal entries has rank two with probability exactly π/4 and rank three with probability $1 - \pi/4$ — two typical ranks, where a random matrix has one, its largest. The essay drew the share converging on π/4 over twenty thousand draws and explained it through Cayley’s hyperdeterminant: rank two when it is positive, three when it is negative.

The hyperdeterminant is special to 2 × 2 × 2, but the phenomenon is not. A tensor of shape n × n × 2 is a pair of n × n matrices — its two slices A and B along the third index — and its real rank is decided by the pencil they form. When A is invertible, the tensor has rank n exactly when the eigenvalues of $A^{-1}B$ are all real and distinct, and rank n + 1 otherwise; this is JáJá’s theorem, and ten Berge’s account of typical ranks for these shapes. So n and n + 1 are both typical ranks at every n — each happens with positive probability — and the share of rank n is the probability that a random real pencil has only real eigenvalues. At n = 2, a 2 × 2 pencil has two real eigenvalues or none, and the hyperdeterminant’s sign is the discriminant that decides which.

What the earlier essay could not show is what happens to the two ranks as the slices grow. Both stay typical. The question is how typical, and it is a question with a number for an answer at every n, which this essay measures and then explains from a closed form it can check.

Rank n, counted and built #

For each n from 2 to 10, the slices A and B are drawn with independent standard normal entries — twenty thousand pairs for n up to 4, ten thousand at 5 and 6, four thousand at 8 and 10 — the eigenvalues of $A^{-1}B$ are computed with the collection’s own real Schur factorisation, and an eigenvalue counts as real when its imaginary part is below $10^{-9}$ of its size.

A count of eigenvalues is a count, not a rank. So for every draw the count says has rank n, the decomposition is built. With V the matrix of eigenvectors, $A = (AV)\,V^{-1}$ and $B = (AV)\,\Lambda\,V^{-1}$, which is n rank-one terms: the i-th column of AV, times the i-th row of $V^{-1}$, times the vector $(1, \lambda_i)$ along the third index. Rebuilding both slices from those n terms and comparing with the tensor gives a relative residual that is worst at $8.9 \cdot 10^{-12}$ over all 32,037 rank-n draws.

Every rank-n count below is therefore a decomposition found, not a test passed. The other direction — that a pencil with a complex pair has no real decomposition with n terms — is the theorem’s, and is not rebuilt here; what can be checked is that the n + 1 case needs the extra term, which a nearest point that is not there showed in its sharpest form, a tensor approached by lower-rank ones that never reach it.

The share of rank n #

At n = 2 the share is 0.7856, against π/4 = 0.7854, the earlier essay’s number reached by a different route. At n = 3 it is 0.5003 — a half, to within the draws’ standard error of 0.0035. After that it falls steeply: 0.2636 at n = 4, 0.1031 at 5, 0.0385 at 6, 16 draws in 4,000 at 8, and at n = 10 none in 4,000. The logarithm of the share falls faster than linearly in n, and through the sizes with any rank-n draws it fits $e^{-0.087 n^2}$ — a Gaussian in n, the same shape as Edelman’s result that a random real n × n matrix has all its eigenvalues real with probability $2^{-n(n-1)/4}$, with about half that exponent.

So “two typical ranks” is true at every n and means very different things. At n = 2 it means a coin weighted three to one. At n = 6 it means that the lower rank turns up once in twenty-six draws. At n = 10 it means an event with positive probability that four thousand draws did not produce. A statement that a shape of tensor has typical ranks {n, n + 1} is exact and, above n of about six, a statement about rank n + 1 in all but name.

A ratio of two keeps its eigenvalues real more often than one #

Edelman’s result for a single matrix is a useful yardstick, because it has a closed form and the pencil’s share, as far as this essay knows, does not. A single n × n matrix with independent standard normal entries has only real eigenvalues with probability exactly $2^{-n(n-1)/4}$: 0.7071 at n = 2, 0.3536 at 3, 0.125 at 4, 0.0313 at 5, 0.0055 at 6.

Measured with the same eigenvalue routine and the same threshold, single matrices land on that formula to within the draws’ error at every size — 0.7072, 0.3537, 0.1220, 0.0311, 0.0054 — which checks the counting as well as the formula. The pencils land well above it: 0.786, 0.500, 0.264, 0.103 and 0.0385. At n = 6 a pencil keeps its eigenvalues real seven times as often as a single matrix does. A ratio $A^{-1}B$ of two Gaussian matrices is not a Gaussian matrix, and whatever makes its eigenvalues cling to the real line more than one matrix’s do is the same thing that halves the exponent of the Gaussian-in-n fall. For the tensor, that difference is the difference between the lower rank being rare and being very rare.

Why the real eigenvalues run out #

The distribution of the number of real eigenvalues says why. At n = 6 the pencil has no real eigenvalues on 4.1 per cent of draws, two on 49.1, four on 42.9 and six — the rank-6 case — on 3.9. The count always has the parity of n, because complex eigenvalues of a real pencil come in conjugate pairs. Turn the dial: at n = 2 the last bar is the tallest, at n = 3 it is half, and from n = 4 the bulk of the distribution sits well below n and the last bar shrinks towards nothing.

The centre of that distribution has a closed form. Edelman, Kostlan and Shub showed that the expected number of real eigenvalues of a pencil of two independent Gaussian n × n matrices is

$$\mathbb{E}[\#\text{real}] = \sqrt{\pi}\,\frac{\Gamma\!\left(\frac{n+1}{2}\right)}{\Gamma\!\left(\frac{n}{2}\right)},$$

which grows like $\sqrt{\pi n/2}$. The measured means are 1.571, 2.001, 2.364, 2.638, 2.930, 3.428 and 3.828 at n = 2 to 10, against the formula’s 1.571, 2.000, 2.356, 2.667, 2.945, 3.436 and 3.866 — within two per cent at every size, and exact at n = 2, where π/2 is twice π/4 because the count is two or zero. The rank-n event needs all n eigenvalues real, and the typical pencil has about the square root of n of them. The distance between n and $\sqrt{\pi n/2}$ is what makes the event rare, and it grows with n.

Rarer, and less sound when found #

The decompositions that do exist change with n as well. Each is built from the eigenvector matrix V of the pencil, and its n rank-one terms cancel against one another by as much as V is far from orthogonal: the condition number of V is the factor by which an error in the tensor can reappear, amplified, in the terms. A tensor that cannot be decomposed measured that amplification directly on a sequence whose terms are known in closed form, where a fit started at the answer lost digits at the rate the conditioning predicts.

On the rank-n draws the median condition number of V is 1.7 at n = 2, 3.2 at 3, 5.1 at 4, 7.3 at 5, 10.0 at 6 and 22 at 8; the ninetieth percentile runs from 4.3 to 108. The largest, 980, is at n = 2, on a draw whose two real eigenvalues nearly coincide — the boundary between the two ranks, where an eigenvector matrix becomes singular. So as n grows the rank-n case becomes both rarer and, when it occurs, a decomposition whose terms carry more cancellation. Neither trend is large at these sizes. Both point the same way: the lower typical rank is a thinner and thinner slice of the space, and a slice near its own edge.

What the family says about the 2 × 2 × 2 case #

The earlier essay’s π/4 now reads as the first term of a sequence rather than a curiosity of the smallest case. It is large because at n = 2 the expected count of real eigenvalues, π/2, is already most of the way to 2. At n = 3 the expected count is exactly 2 and the share of all-real pencils is a half; at every larger n the expected count falls further behind n.

It also says something about the claim, true in a rank that is not a property of the tensor, that the rank depends on the field. Over the complex numbers every one of these pencils has n eigenvalues, all of them distinct with probability one, and every n × n × 2 tensor has complex rank n. The gap between the real and the complex rank is exactly the complex pairs — one extra real term for the pencil as a whole, however many pairs there are, since the real rank is n + 1 whenever it is not n. So over the reals the typical rank is n + 1 in practice and the complex rank is n always, and the field-dependence the earlier essay found in one tensor is, for this family, the ordinary case. The orthogonality that cannot be diagonal found the other half of what a tensor gives up against a matrix: no decomposition has both orthogonal factors and a diagonal core. Here the loss is in the count itself, and it is decided by the field the numbers live in.

What “typical” was ever claiming #

A rank is typical for a shape when the tensors having it fill a set of positive volume — an open region of the space, which a random draw from any continuous distribution lands in with positive probability. For n × n matrices only one rank is typical, n, because the singular matrices are a surface of zero volume. For n × n × 2 real tensors two are, n and n + 1, because the pencils with all-real eigenvalues and the pencils with a complex pair are each an open region, separated by the surface where two eigenvalues collide. The definition is about which regions exist, and it is silent on how large they are.

What the measurement adds is the size of the smaller region under the most natural distribution there is, and the size falls like a Gaussian in n. That makes “typical” a word to read with its measure attached. A statement in a paper that a shape has typical ranks {5, 6} is exact; a practitioner who draws random 5 × 5 × 2 tensors to test a rank-5 method will find one in ten usable, and at 8 × 8 × 2 one in 250. The same gap between existence and frequency runs through tensor rank generally: a nearest point that is not there is about a set that exists and whose infimum is not attained, and one term too many about a fit whose spare term has a place to go and does not go there.

What an algorithm meets #

A computation that fits a CP decomposition of rank n to an n × n × 2 tensor — alternating least squares or any other — meets this directly; a decomposition made only of SVDs is the collection’s way round the question, a Tucker format whose existence does not depend on the rank. On the rank-n draws an exact fit exists and the eigenvector construction above finds it in one eigenvalue problem. On the others, the best rank-n approximation may not exist at all: rank n + 1 tensors with a complex pair are approached by rank-n ones whose terms grow without bound, the phenomenon a nearest point that is not there measured for 2 × 2 × 2. At n = 6 that is the situation on 96 draws in a hundred, and at n = 10 essentially always. A method that asks for rank n on this shape is asking for the rare case, and an iteration that walks out of the set is what an alternating fit does on the common one: its terms grow without bound while its residual falls towards a value no rank-n tensor attains.

The practical rule is the eigenvalue count. It is the same kind of rule the rank a sweep can vouch for looked for in an alternating fit — a number the computation can produce that says which case it is in — with the difference that here the number is exact and cheap. Computing the pencil’s eigenvalues costs one n × n eigenvalue problem; if they are all real the decomposition is in hand, and if any pair is complex the tensor needs n + 1 terms, and a rank-n fit should be expected to diverge rather than to converge.

Only the n × n × 2 shape, only normal entries #

Only the n × n × 2 shape, with independent standard normal entries. Other distributions change the probabilities — a pencil whose slices are nearly simultaneously diagonalisable has all-real eigenvalues far more often — and other shapes have other typical ranks, most of them not known in closed form. The sweep stops at n = 10 with four thousand draws, so the share there is known only to be below about $10^{-3}$; the Gaussian-in-n fit is a fit through five points, not a derivation, and the exponent 0.087 is stated to that precision and no further.

The complex rank n of the other draws is the theorem’s and is not rebuilt: building those decompositions needs complex eigenvectors and complex terms, and a residual of the same kind would check them, which this sweep did not do. An eigenvalue with imaginary part below $10^{-9}$ of its size is counted as real. A pencil with a nearly real complex pair, or a nearly repeated real pair, sits on the boundary between the two ranks, and the count there depends on that threshold; the boundary has measure zero, and the built decompositions’ residuals — none above $10^{-11}$ — say that no draw counted as rank n was a boundary case in disguise.

Still open: the exact shares, and the shapes beyond #

The shares in closed form. The measured shares are π/4 at n = 2 and a half at n = 3, both to within the draws’ error, and the exponent of the Gaussian-in-n fall is about 0.087. Whether the probability that a Gaussian pencil has only real eigenvalues has a closed form of Edelman’s kind — and whether its exponent is exactly half of $\log 2/4$ — is a question with a sign: the fit says it is close to half, and a closed form would say whether it is exactly.

The n × n × 3 shape. Three slices give a tensor whose typical real ranks are larger than n and not decided by one pencil. Whether the lower of them also becomes rare as n grows, and at what rate, would say whether the disappearance measured here is a property of pencils or of real tensors generally.

What a rank-n fit does on the common case. On a draw whose pencil has a complex pair, an alternating least-squares fit of rank n cannot converge to an exact decomposition and may not converge at all. How its residual and the size of its terms behave over iterations — whether it looks like the swamps alternating least squares is known for or like a divergence — is measurable on the same draws, and it is the version of this result an algorithm meets.