🔢 mathematics

On the Number of Cholesky Roots of the Zero Matrix over F2

This paper investigates the number of Cholesky roots of the zero matrix over the finite field F2 and establishes a rank-preserving bijection between these roots and the upper-triangular square roots of the zero matrix.

Original authors: Hays Whitlatch

Published 2026-08-10

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Hays Whitlatch

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 are a master architect working in a very strange, tiny world made entirely of just two types of bricks: "Off" (zero) and "On" (one). In this world, called the field of two elements ( $\mathbb{F}_2$ ), the rules of construction are different. If you stack two "On" bricks on top of each other, they magically cancel out and become "Off." This is the world of finite fields, a playground for mathematicians who study how numbers behave when they wrap around like clock hands.

In the real world, we often use a tool called a "Cholesky decomposition" to break down complex shapes into simpler, triangular pieces. Think of it like taking a complicated, symmetrical sculpture and figuring out exactly which triangular blocks were used to build it. Usually, for a specific sculpture, there is only one correct way to do this. But in our tiny two-brick world, things get messy. Sometimes, a sculpture made of "Off" bricks (a zero matrix) can be built in many, many different ways using triangular blocks. The question isn't just "can we build it?" but "how many different blueprints exist?" This matters because these patterns show up in cryptography (secret codes), error-correcting messages, and understanding the deep structure of numbers.

This paper, written by Hays Whitlatch, dives into that messy, magical world to count exactly how many different triangular blueprints can build a "zero" sculpture. The author proves a surprising and beautiful connection: the number of ways to build a zero matrix using triangular blocks is exactly the same as the number of ways to build a "zero" square root (where a block multiplied by itself equals zero) and the same as the number of ways to build a square root of the identity matrix (where a block multiplied by itself equals the standard "do nothing" block)—but this specific equivalence only holds true within this two-brick world ( $\mathbb{F}_2$ ).

The paper doesn't just guess; it provides a rigorous mathematical proof. It shows that for any size of matrix in this specific field, there is a perfect, rank-preserving match between these three different sets of solutions. In other words, if you know how many ways you can make a zero square root, you instantly know how many ways you can make a Cholesky root of zero. The author also provides a specific formula to calculate these numbers for matrices over $\mathbb{F}_2$ , showing that for larger matrices, the number of solutions grows incredibly fast, following a complex pattern involving sums of combinations.

However, the paper is careful to point out that this magic trick only works in the two-brick world. If you try to use these same counting rules in a world with more brick types (other finite fields), the connection breaks because the math behaves differently. The author concludes that while we now have a precise count for the two-brick world, figuring out how to count these roots in other worlds will require entirely new tools and techniques. The work is a definitive proof for this specific case, not a simulation or a suggestion, offering a clear map for a very specific, yet fundamental, corner of mathematics.

Technical Summary: On the Number of Cholesky Roots of the Zero Matrix over F2

Problem Statement
This paper investigates the enumeration of distinct Cholesky factorizations for matrices with entries in the finite field with two elements, $\mathbb{F}_2$ . Specifically, the author focuses on the zero matrix, $0_n$ . A matrix $U$ is defined as a Cholesky root of a symmetric matrix $M$ if $U^T U = M$ , where $U$ is an upper-triangular matrix. While Cholesky factorizations over real or complex fields are unique for positive-definite matrices (and the zero matrix over $\mathbb{C}$ has a unique root, the zero matrix itself), uniqueness is lost over finite fields and for positive-semidefinite matrices. The central problem addressed is determining the exact count of such upper-triangular matrices $U$ satisfying $U^T U = 0_n$ over $\mathbb{F}_2$ , categorized by the rank of $U$ .

Methodology
The author employs a combinatorial and inductive approach to analyze the structure of upper-triangular matrices over $\mathbb{F}_2$ . The methodology relies on defining three specific sets of $n \times n$ upper-triangular matrices:

$A_n(r)$ : Matrices $U$ of rank $r$ such that $U^2 = I_n$ (roots of the identity).
$B_n(r)$ : Matrices $U$ of rank $r$ such that $U^2 = 0_n$ (square roots of the zero matrix).
$C_n(r)$ : Matrices $U$ of rank $r$ such that $U^T U = 0_n$ (Cholesky roots of the zero matrix).

The proof strategy involves establishing a rank-preserving bijection between these sets.

Bijection between $A_n$ and $B_n$ : The author observes that in $\mathbb{F}_2$ , $(X + I_n)^2 = X^2 + I_n$ . This algebraic property implies a direct correspondence where $X^2 = 0_n$ if and only if $(X + I_n)^2 = I_n$ , proving $|A_n| = |B_n|$ .
Bijection between $B_n$ and $C_n$ : The core of the paper is an inductive proof showing $|B_n(r)| = |C_n(r)|$ for all $n$ and $r$ . By partitioning the matrices based on their principal $(n-1) \times (n-1)$ submatrices and analyzing the constraints on the remaining row/column vectors (specifically relating to the null space and column space of the submatrix), the author derives identical recurrence relations for the cardinalities of $B_n(r)$ and $C_n(r)$ .
Utilization of Existing Literature: The paper leverages a known counting formula for the number of upper-triangular matrices whose square is zero (cited from reference [3]) to provide a closed-form summation for the counts.

Key Contributions and Results

Rank-Preserving Bijection: The primary theoretical contribution is the proof that there exists a rank-preserving bijection between the set of Cholesky roots of the zero matrix ( $C_n$ ) and the set of upper-triangular square roots of the zero matrix ( $B_n$ ). Consequently, the number of Cholesky roots of $0_n$ is equal to the number of upper-triangular matrices $U$ such that $U^2 = 0_n$ .
Exact Counting Formula: By combining the bijection with the result from reference [3], the paper provides a closed-form summation formula for the total number of Cholesky roots of the zero matrix of size $n$ :
$|C_n| = \sum_{j} \left[ \binom{n}{\lfloor n/2 \rfloor - 3j} - \binom{n}{\lfloor n/2 \rfloor - 3j - 1} \right] 2^{\lfloor n/2 \rfloor \lceil n/2 \rceil - 3j^2 - (\lceil n/2 \rceil - \lfloor n/2 \rfloor + 1)j}$
The paper also notes that for rank $r \ge n/2$ , the set of such matrices is empty.
Application to Leading Principal Non-Singular (LPN) Matrices: The paper establishes that for a symmetric matrix $M$ of rank $r$ in "leading principal non-singular" (LPN) form, the number of distinct Cholesky factorizations is exactly $|C_n(n-r)|$ . This links the general counting problem to specific classes of symmetric matrices.

Significance and Scope
The paper modestly frames its contribution as an enumeration problem within finite field linear algebra. It highlights that the uniqueness of Cholesky factorization, a standard property in real and complex analysis, fails over $\mathbb{F}_2$ . The significance lies in providing a precise combinatorial count for these non-unique factorizations.

The author explicitly notes limitations and boundaries of the current work:

The bijection between Cholesky roots of zero, square roots of zero, and square roots of the identity relies on the specific property $(X+I)^2 = X^2 + I$ , which is unique to $\mathbb{F}_2$ . Therefore, these techniques do not extend to other finite fields.
The counting formula for LPN matrices does not apply to symmetric matrices not in LPN form, as demonstrated by a counterexample in the text.
While the paper observes the asymptotic behavior of the terms in the summation, it cautions that the summands can be negative, preventing the immediate use of the largest term as a simple lower bound for the total count.

The paper concludes by identifying the asymptotic behavior of $|C_n(r)|$ and the extension of these counting techniques to other finite fields as potential directions for future work.

More like this