Schur complements for tensors and multilinear commutative rank

This paper establishes the equivalence of three notions of rank for matrices of multilinear forms, thereby generalizing Flanders' classical result, correcting prior work by Fortin and Reutenauer, resolving a question posed by Lampert, and proving a special case of the conjecture linking analytic and partition ranks of tensors.

The Gist

Imagine you are trying to measure the "complexity" of a giant, multi-dimensional puzzle. In mathematics, these puzzles are called tensors (think of them as cubes or hypercubes of numbers, rather than just flat sheets like a 2D matrix).

The paper by Guy Moshkovitz and Daniel G. Zhu is about figuring out how to measure the complexity of these puzzles in three different ways, and proving that these three ways are actually saying the same thing, just with slightly different numbers.

Here is the breakdown using simple analogies:

1. The Three Ways to Measure Complexity

Imagine you have a giant, magical recipe book (the tensor) that tells you how to mix ingredients ($x_1, x_2, \dots$) to get a result. You want to know how "complicated" this recipe is. The authors look at three different definitions of complexity:

• The "Max-Rank" (The Best Performance):
  Imagine you test this recipe with every possible combination of ingredients you can find in your kitchen. What is the highest level of "output" or "rank" you ever get? This is the Max-Rank. It's like asking, "What is the best this machine can do if I tweak the knobs perfectly?"

• The "Commutative Rank" (The Theoretical Potential):
  Now, imagine you don't just test the machine; you look at the blueprint itself. You treat the ingredients as variables in a giant algebraic equation. You ask, "If I could use any numbers (even infinite ones), how complex is the underlying structure?" This is the Commutative Rank. It's the theoretical maximum complexity hidden inside the formula.

• The "Partition Rank" (The Construction Cost):
  This is the most practical definition. Imagine you want to build this complex machine from scratch using simple, pre-made Lego blocks. Each "block" is a simple product of two smaller parts. The Partition Rank is the minimum number of blocks you need to stack together to recreate the whole machine.

  • Analogy: If you have a complex sculpture, the Partition Rank is the fewest number of simple clay shapes you need to smash together to make it.

2. The Problem: They Usually Don't Match

For a long time, mathematicians knew that for simple 2D puzzles (matrices), these three measurements were roughly the same. But for complex, multi-dimensional puzzles (where $d > 1$), they thought these measurements might be totally different.

• The Max-Rank might be low (the machine doesn't do much in practice).
• The Commutative Rank might be high (the blueprint looks very complex).
• The Partition Rank might be huge (you need a mountain of Lego blocks to build it).

The big question was: If the blueprint looks complex, does that mean the machine is actually hard to build?

3. The Big Discovery: They Are Equivalent

The authors proved that yes, they are all connected.

If the blueprint (Commutative Rank) says the puzzle is complex, then the machine is actually hard to build (Partition Rank), and vice versa. They aren't equal numbers, but they are proportional. If one goes up, the others must go up too.

The Formula:
They found a rule that says:

The number of Lego blocks you need (Partition Rank) is at most a constant number times the complexity of the blueprint (Commutative Rank).

The "constant" depends on how many dimensions the puzzle has (how many variables are in the recipe).

4. The Secret Weapon: The "Schur Complement"

How did they prove this? They used a clever mathematical trick called the Schur Complement, which they adapted for these multi-dimensional puzzles.

The Analogy:
Imagine you have a giant, messy pile of Lego blocks (the complex tensor). You want to break it down into simple pieces.

1. Find a solid core: You find a small, perfect square section of the puzzle that is easy to solve (an invertible submatrix).
2. Peel it off: You use a mathematical "peeler" (the Schur complement) to remove that core.
3. The Magic: When you peel off that core, the messy pile you are left with is simpler than the original. It has lower complexity.
4. Repeat: You keep peeling off cores. Each time, you save a few simple Lego blocks (the part you peeled off) and are left with a smaller, simpler puzzle.
5. Finish: Eventually, the whole puzzle is gone, and you have a pile of simple blocks.

The Twist:
Usually, when you do this peeling, the math gets messy because you have to divide by things, creating "fractions" (rational functions) that break the rules of the puzzle (multilinearity). The authors invented a way to approximate these messy fractions with clean, simple polynomials, allowing them to keep peeling without breaking the rules.

5. Why Does This Matter?

This isn't just about abstract math; it solves real problems in computer science and cryptography.

• Fixing Old Mistakes: They corrected a small error in a famous 20-year-old paper by Fortin and Reutenauer.
• Answering a Question: They solved a puzzle posed by a researcher named Lampert regarding how "analytic" complexity relates to "slice" complexity in 3D tensors.
• The "Small Field" Breakthrough: Most previous math worked well only if you had an infinite supply of numbers. This paper works even if you are working with very small, limited sets of numbers (like in computer encryption). They broke through a "logarithmic barrier" that had stopped progress for years.

Summary

Think of this paper as a master key. For years, mathematicians had three different keys (Max-Rank, Commutative Rank, Partition Rank) that they thought opened different doors. Moshkovitz and Zhu showed that these keys actually open the same door, just with different amounts of turning. They did this by inventing a new way to "peel" complex puzzles layer by layer, proving that if a puzzle looks complex on paper, it is genuinely complex to build, no matter how small your number set is.

Technical Summary

Here is a detailed technical summary of the paper "Schur Complements for Tensors and Multilinear Commutative Rank" by Guy Moshkovitz and Daniel G. Zhu.

1. Problem Statement and Context

The paper addresses the relationship between three distinct notions of rank for matrices whose entries are multilinear forms (polynomials linear in each of $d$ sets of variables). Let $M$ be an $L$-matrix where $L$ is the space of multilinear forms over a field $\mathbb{F}$. The three ranks are:

1. Max-Rank ($MR(M)$): The maximum rank of the matrix $M(x_1, \dots, x_d)$ when evaluated at specific points $x_i \in \mathbb{F}^n$.
2. Commutative Rank ($CR(M)$): The rank of $M$ when viewed as a matrix over the field of rational functions in the variables. Equivalently, the size of the largest non-vanishing minor (as a polynomial).
3. Partition Rank ($PR(M)$): The minimum number of multilinear outer products (rank-1 tensors) required to sum to $M$.

The Core Problem:
While it is trivial that $MR(M) \le CR(M) \le PR(M)$, these quantities are generally distinct. The paper seeks to establish whether these ranks are equivalent up to constant factors, particularly over small finite fields. This is a specific instance of the broader Analytic Rank vs. Partition Rank Conjecture, which posits that for any tensor $T$, $PR(T) \le C \cdot AR(T)$ (where $AR$ is analytic rank).

Previous work had established these equivalences for large fields or specific cases (e.g., $d=1$), but gaps remained for small fields and higher degrees ($d \ge 2$). Specifically, a "logarithmic gap" had persisted in general tensor rank bounds over small fields.

2. Methodology

The authors develop a novel algebraic framework centered on Schur Complements adapted to the multilinear setting.

A. Differential Schur Complements

Standard Schur complements involve inverting a submatrix $A$. In the context of multilinear forms, inverting a submatrix $A$ (where entries are polynomials) typically results in rational functions, thereby destroying the multilinearity of the remaining entries.

To overcome this, the authors introduce a Differential Schur Complement:

1. Localization: They work in the ring of rational functions localized at a point $p$ where a submatrix $A(p)$ is invertible.
2. Approximation Map: They define a linear map $[\cdot]_p$ that approximates a rational function by a multilinear polynomial. This map is defined via directional derivatives:
   $$[f]_p(y) = \frac{\partial}{\partial t_1} \cdots \frac{\partial}{\partial t_d} f(p_1 + t_1 y_1, \dots, p_d + t_d y_d) \Big|_{t=0}$$
   This operation effectively extracts the "multilinear part" of the rational function near $p$.
3. Decomposition: They define the differential Schur complement as $[M/A]_p$. Crucially, they prove that the difference $M - [M/A]_p$ can be written as a sum of a bounded number of outer products (specifically $\le 2dr$ for an $r \times r$ submatrix).

B. Iterative Reduction

The proof strategy involves an iterative process:

1. Find a submatrix $A$ that is invertible at some point $p$.
2. Compute the differential Schur complement $M' = [M/A]_p$.
3. The "error" term $M - M'$ has low partition rank.
4. The new matrix $M'$ has a strictly lower commutative rank than $M$ (under specific conditions).
5. Repeat the process until the remainder is zero.

C. Method of Multiplicities

To bound the rank reduction and ensure the process terminates efficiently, the authors employ the method of multiplicities. They utilize a generalized Schwartz-Zippel lemma to show that a non-zero polynomial cannot vanish to high order at too many points. This allows them to prove that for a matrix of commutative rank $r$, there exists a point $p$ where the evaluation rank is sufficiently high (close to $r$), ensuring the iterative step reduces the rank significantly.

3. Key Contributions and Results

Main Theorem (Theorem 1.1)

The authors prove that for any $d$-linear matrix $M$ over a field $\mathbb{F}$ (finite or infinite):
$$PR(M) \le (2d + O_d(|\mathbb{F}|^{-1})) \cdot CR(M)$$
$$CR(M) \le \left(1 - \frac{1}{|\mathbb{F}|}\right)^{-d} \cdot MR(M)$$

• Significance: This establishes that the three ranks are equivalent up to constants depending only on the degree $d$ and field size.
• Tightness: The constant $(1 - 1/|\mathbb{F}|)^{-d}$ is proven to be tight. The factor $2d$is known to be tight for$d=1$.

Corollary 1.3 (Linear Matrices, $d=1$)

For matrices of linear forms, $PR(M) \le 2 CR(M)$.

• Context: This corrects a minor oversight in the work of Fortin and Reutenauer regarding the field size restriction in Flanders' theorem and unconditionally proves the equivalence of non-commutative rank and partition rank for linear matrices.

Corollary 1.5 (3-Tensors)

For any 3-tensor $T$ over a finite field $\mathbb{F}_q$:
$$SR(T) \le \left(3 + \frac{2}{q-1}\right) AR(T)$$

• Context: This improves upon previous bounds (which had a constant of 5 or relied on geometric invariant theory) and answers a question by Lampert. It establishes a linear relationship between Slice Rank and Analytic Rank for 3-tensors with an explicit constant.

4. Significance and Impact

1. Breaking the Logarithmic Barrier: Previous results on the equivalence of Partition Rank and Analytic Rank (e.g., by the authors themselves in [MZ22]) included a logarithmic factor: $PR(T) \le C \cdot AR(T) \cdot (1 + \log_q AR(T))$. This paper breaks that barrier for a specific but important class of objects (matrices of multilinear forms), establishing linear bounds.
2. Unification of Concepts: The work unifies the study of matrix ranks over fields with the study of tensor ranks. It demonstrates that techniques from linear algebra (Schur complements) can be successfully generalized to the multilinear setting via differential approximation.
3. Correction of Literature: It rectifies a subtle error in the application of Flanders' theorem by Fortin and Reutenauer, clarifying the relationship between non-commutative rank and partition rank without assuming large fields.
4. Pathway to General Conjecture: While the result applies to matrices of multilinear forms (a special case of tensors), the authors suggest that their "multi-level Schur complement" approach could be the key to proving the general Analytic Rank-Partition Rank conjecture for arbitrary tensors. The main obstacle remaining is extending the "almost total decomposition" step to higher-degree polynomials where the method of multiplicities is less effective.

Summary

Moshkovitz and Zhu successfully generalize the concept of Schur complements to multilinear forms by introducing a differential approximation technique. This allows them to iteratively decompose matrices of multilinear forms, proving that their partition rank is linearly bounded by their commutative rank. This result resolves long-standing questions about the equivalence of various tensor ranks over small fields and provides a powerful new tool for the algebraic complexity theory of tensors.