🔢 mathematics

On the submatrices with the best-bounded inverses

This paper provides a proof for the case $k=2$ of the hypothesis by Goreinov, Tyrtyshnikov, and Zamarashkin, which asserts that any $n \times k$ real matrix with orthonormal columns contains a $k \times k$ submatrix with a smallest singular value of at least $\frac{1}{\sqrt{n}}$ .

Original authors: Richik Sengupta, Mikhail Pautov

Published 2026-04-08

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Richik Sengupta, Mikhail Pautov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, perfectly organized dance troupe. This troupe has $n$ dancers (rows), but they are only performing a routine that requires 2 specific moves (columns). Because they are professional, their movements are perfectly synchronized and balanced (orthonormal columns).

The big question mathematicians have been asking is: If you look at any group of just 2 dancers from this huge troupe, can you always find a pair whose movements are "strong enough" on their own?

Specifically, the hypothesis says: No matter how big the troupe is, there is always at least one pair of dancers whose combined "strength" (mathematically, the smallest singular value of their 2x2 submatrix) is at least $1/\sqrt{n}$ .

For a long time, this was just a guess supported by computer simulations. It worked for small groups, but no one could prove it for medium-sized groups. This paper, by Richik Sengupta and Mikhail Pautov, finally proves it works when the routine involves exactly 2 moves ( $k=2$ ).

Here is how they solved the puzzle, broken down into two scenarios:

Scenario A: The "Weak Link" Strategy

Imagine you scan the whole troupe and find one dancer who is moving very slowly or weakly (their row norm is small).

The Trick: The authors say, "Okay, let's ignore that weak dancer for a second."
The Logic: If you remove that weak dancer, you are left with $n-1$ dancers. By a mathematical rule called "induction" (which is like saying, "If it works for a group of 10, it works for 9, and so on"), we know that among the remaining $n-1$ dancers, there is a strong pair.
The Twist: What if the weak dancer isn't that weak? The authors use a clever "rotation" (like spinning the whole stage) to align the data so that the math becomes easier. They show that even if you have to stretch the remaining dancers slightly to make them fit, the "strong pair" you found in the smaller group is still strong enough to satisfy the rule for the original big group.

Analogy: It's like finding the best two players on a basketball team. If one player is terrible, you just look at the rest of the team. The math proves that even if you have to adjust for that one bad player, the remaining team still has a "championship duo" hidden inside.

Scenario B: The "Everyone is Strong" Strategy

Now, imagine the opposite. Every single dancer is moving with high energy. No one is weak; everyone's "norm" is greater than $1/\sqrt{n}$ .

The Problem: If everyone is strong, how do we prove there is a specific pair that works together well? Just because everyone is strong individually doesn't mean they don't trip over each other when paired up.
The Detective Work: The authors treat the dancers as vectors (arrows) and look at how they relate to each other. They invent a new set of "shadow vectors" (called $w_i$ ) that represent the relationship between the dancers' moves.
The Contradiction: They assume the opposite of what they want to prove: "What if every single pair of dancers is a bad match?"
- They build a giant "compatibility matrix" (a grid showing how well everyone gets along).
- Using advanced linear algebra (eigenvalues and the Perron-Frobenius theorem, which sounds scary but is basically about how positive numbers behave in a group), they show that this assumption leads to a logical impossibility.
- The Metaphor: It's like saying, "If every single pair of people in a room hates each other, but everyone is also very friendly on average, the math breaks." The universe of numbers simply cannot exist in that state.
The Result: Since the assumption that "everyone is a bad pair" leads to a contradiction, there must be at least one pair that gets along perfectly (or at least well enough).

The Grand Conclusion

By combining these two strategies:

If there's a weak dancer, we use the "rotation and induction" trick.
If everyone is strong, we use the "contradiction" trick to prove a good pair must exist.

The authors have successfully proven that for any large group of synchronized dancers performing 2 moves, you can always find a duo that is strong enough to carry the show.

Why does this matter?
In the real world, this math is used in signal processing, data compression, and machine learning. It assures engineers that when they break down massive, complex data sets into smaller chunks, they won't accidentally lose all the important information. There is always a "golden pair" of data points that preserves the integrity of the whole system.

1. Problem Statement

The paper addresses a long-standing open problem in linear algebra and matrix theory, originally formulated by Goreinov, Tyrtyshnikov, and Zamarashkin. The core hypothesis concerns the existence of well-conditioned submatrices within matrices having orthonormal columns.

Hypothesis 1:
Let $U$ be an $n \times k$ real matrix with orthonormal columns (where $n > k$ ). The hypothesis states that there exists a $k \times k$ submatrix $Q$ of $U$ such that the spectral norm of its inverse does not exceed $\sqrt{n}$ . Equivalently, the smallest singular value of $Q$ , denoted $\sigma_k(Q)$ , satisfies:
$\sigma_k(Q) \geq \frac{1}{\sqrt{n}}$

Context:

The problem is trivial for $k=1$ and $n \leq 4$ (with specific cases like $n=4, k=2$ already proven by Y. Nesterenko).
For all non-trivial cases where $1 < k < n-1$ , the problem remained open despite numerical evidence supporting the hypothesis.
Goal of this paper: To provide a rigorous proof for the specific case where $k=2$ for all $n > 2$ .

2. Methodology

The authors employ a mathematical induction strategy on the number of rows $n$ , combined with a case-based analysis of the row norms of the matrix.

Inductive Framework

Base Cases: The proof assumes the hypothesis holds for $n-1$ rows. The cases for $n=3$ (trivial) and $n=4$ (previously proven) serve as the foundation.
Inductive Step: Assume the hypothesis is true for any $(n-1) \times 2$ matrix with orthonormal columns. The authors then prove it for an $n \times 2$ matrix $A$ (where $A^T A = I$ ).

Case Analysis

The proof splits into two distinct cases based on the Euclidean norms of the rows of matrix $A$ :

Case A: Existence of a "Small" Row

Condition: At least one row $i$ has a squared norm $\|r_i\|^2 \leq \frac{1}{n}$ .
Technique:
1. A rotation matrix $P$ is applied to $A$ to transform the small row into a vector $(b, 0)$ , where $b^2 \leq 1/n$ .
2. If $b=0$ , the first row is removed, leaving an $(n-1) \times 2$ matrix with orthonormal columns. By the induction hypothesis, a valid submatrix exists with $\sigma_2 \geq 1/\sqrt{n-1} \geq 1/\sqrt{n}$ .
3. If $b > 0$ , the authors construct a scaled submatrix $\hat{C}$ from the remaining $n-1$ rows. They utilize the invariance of singular values under rotation and the property $\sigma_2(YZ) \geq \sigma_2(Y)\sigma_2(Z)$ .
4. Through algebraic manipulation, they show that the smallest singular value of the resulting $2 \times 2$ submatrix satisfies $\sigma_2 \geq \sqrt{\frac{1-b^2}{n-1}}$ . Since $b^2 \leq 1/n$ , this value is bounded below by $1/\sqrt{n}$ .

Case B: All Rows are "Large"

Condition: For all rows $i$ , $\|r_i\|^2 > \frac{1}{n}$ .
Technique: This is the more complex part of the proof, utilizing spectral graph theory and eigenvalue analysis.
1. Vector Transformation: The rows $r_i = (x_i, y_i)$ are mapped to new vectors $w_i = (x_i^2 - y_i^2, 2x_iy_i)$ . Key properties established are $\sum w_i = 0$ and $\|w_i\|^2 = \|r_i\|^4$ .
2. Inequality Formulation: The goal is to find a pair of indices $(i, j)$ such that the squared inner product $(r_i, r_j)^2$ is sufficiently small relative to the norms. This is transformed into an inequality involving $w_i$ and a scalar sequence $z_i = \|r_i\|^2 - 2/n$ .
3. Contradiction via Matrix Rank: The authors define a matrix $G = WW^T - zz^T$ . They assume the desired inequality fails for all pairs, implying all entries of a related matrix $M = G + \frac{2}{n^2}E$ are positive.
4. Eigenvalue Analysis:
  - Using the rank properties of $WW^T$ (rank $\leq 2$ ) and $zz^T$ (rank $\leq 1$ ), they show $G$ has at most 2 positive eigenvalues.
  - They calculate the trace of $G$ to be $4/n$ , implying the largest eigenvalue $\lambda_1 \geq 2/n$ .
  - Applying the Perron-Frobenius theorem to the positive matrix $M$ , they deduce that the eigenvalue corresponding to the all-ones vector ( $2/n$ ) must be the unique largest eigenvalue.
  - However, spectral analysis of $G$ shows that its largest eigenvalue $\lambda_1$ corresponds to an eigenvector orthogonal to the all-ones vector. This leads to a contradiction: $\lambda_1$ must be strictly less than $2/n$ (due to Perron-Frobenius on $M$ ) but the trace calculation requires $\lambda_1 \geq 2/n$ .
5. Conclusion of Case B: The contradiction proves that there must exist a pair $(i, j)$ satisfying the required inequality. This ensures the existence of a $2 \times 2$ submatrix with the smallest singular value $\geq 1/\sqrt{n}$ .

3. Key Contributions

Resolution of the $k=2$ Case: The paper provides the first rigorous proof for the hypothesis when the number of columns $k=2$ , resolving a problem that had remained open for non-trivial $n$ .
Novel Vector Mapping: The introduction of the mapping $r_i \to w_i = (x_i^2 - y_i^2, 2x_iy_i)$ allows the authors to translate geometric properties of the rows into algebraic constraints on vectors in $\mathbb{R}^2$ .
Spectral Contradiction: The proof elegantly combines the trace of a constructed matrix with the Perron-Frobenius theorem to force the existence of a "good" submatrix in the case where all rows are large.

4. Results

The authors successfully prove Hypothesis 1 for all $n > 2$ when $k=2$ .

Result: For any $n \times 2$ matrix with orthonormal columns, there exists a $2 \times 2$ submatrix $Q$ such that $\sigma_2(Q) \geq \frac{1}{\sqrt{n}}$ .
This confirms that the inverse of such a submatrix has a spectral norm bounded by $\sqrt{n}$ .

5. Significance

Theoretical Advancement: This work closes a significant gap in the theory of orthonormal frames and submatrix conditioning. It validates a conjecture that was previously supported only by numerical experiments.
Algorithmic Implications: In numerical linear algebra, algorithms often rely on selecting well-conditioned submatrices (e.g., in QR factorization with column pivoting, sparse matrix approximations, or randomized linear algebra). Knowing that a submatrix with a guaranteed bound exists for $k=2$ provides a theoretical foundation for the stability of such selection strategies in low-dimensional projections.
Foundation for General $k$ : While the proof is specific to $k=2$ , the techniques involving induction, row norm analysis, and spectral properties of constructed matrices may offer a pathway for tackling the general case where $k > 2$ .

In summary, Sengupta and Pautov have provided a complete and rigorous solution to the "best-bounded inverse" problem for the 2-column case, utilizing a sophisticated blend of linear algebra, induction, and spectral theory.