Skip to content
Preprint

Low-rank matrices with three prescribed off-diagonal values over $\mathbb{F}_p$

Oct 2026 · 0 citations · 7 references
Mathematics

Abstract

For every prime $p$ and every three-element set $L\subseteq\mathbb{F}_p$, we prove that, for every integer $n\geq1$, there exists a symmetric $n\times n$ matrix over $\mathbb{F}_p$ with zero diagonal, off-diagonal entries in $L$, and rank $O_{p,L}(n^{1/3})$. This answers a question of Bukh. When $0\notin L$, a standard polynomial argument shows that the exponent $1/3$ is optimal. The proof combines an incidence matrix factorization with a projective-plane construction controlling line-intersection numbers modulo $p$. A separate geometric construction in characteristic two yields better explicit constants in certain cases, and also gives integer lifts $L'$ of the prescribed sets $L$ and symmetric $L'$-matrices of rational rank $O_{p,L}(n^{1/3})$. When $0\notin L'$, this improves Bukh's general quadratic lower bound, giving matrices of order $\Omega_{p,L}(r^3)$ and rational rank at most $r$.

View source

Similar papers

Preprint Nov 2026

Extremal permutations of $\mathbb{Z}_n$ with many good slopes and applications to quantum Latin squares

For $n\ge2$, a good slope of a permutation $f$ of $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$ is an element $m\in\mathbb{Z}_n$ for which $x\mapsto f(x)+mx$ is a permutation. We prove the sharp upper bound $\varphi(n)$ on the number of good slopes, where $\varphi$ is Euler's totient function. We classify and count the equalit...

D. K. Bhunia · 0 citations
Preprint Oct 2026

The rank of $\mathbb{Z}_{2^s}$-linear Hadamard codes

The canonical $\mathbb{Z}_{2^s}$-linear Hadamard codes are the Gray images of the $\mathbb{Z}_{2^s}$-additive codes. Their rank, the dimension of the binary linear span, was known in closed form only for $s\le 3$, and for $s \ge 4$ only through computer computations for small lengths. We give a method that computes the...

Xuan Wang, Min-Jia Shi · 0 citations
Preprint Oct 2026

Exact Rank of the Largest Good Lattice Point Matrix

We prove that for every integer $n>2$ the largest good lattice point matrix $U_n=[u_h:h\in H_n]$, whose columns are generated by all integers $h<n$ coprime to $n$, has rank exactly $\varphi(n)/2+1$. The upper bound follows from the pairing identity $u_h+u_{n-h}=(n,\dots,n,2n)^{\top}$. For the lower bound the columns ar...

Long-Hao Xu · 0 citations
Preprint Oct 2026

An upper bound on the smallest singular value of dense signed random combinatorial matrices

Let $M_n$ be an $n\times n$ random matrix with entries in $\{-1, 0, 1\}$, where each row is independently and uniformly sampled from the set of all vectors in $\{-1, 0, 1\}^n$ containing exactly $d$ nonzero entries, with $d=pn$ for some fixed constant $p\in(0,1/2]$. A recent result by one of the authors gives a lower b...

Yu-Xiao Shi, Ze-Yan Song, Ke-Xin Yu et al. · 1 citation
Preprint Nov 2026

Linear-exponent bounds for the automatic complexity of rational diagonals modulo prime powers

Let $p$ be a prime and let $G$ be the diagonal of $N/Q$ in $m$ variables over the $p$-adic integers, with $Q(0)$ a unit. We prove that the $p$-kernel of the coefficients of $G$ modulo $p^\alpha$ has size $K_\alpha(G)\le p^{(|J|+1)\alpha-1}+(p^\alpha-1)/(p-1)$, where $J$ is an explicit finite support set determined by t...

Alexey A. Shvets · 0 citations
Sep 2026

Matrix-Vector Complexity of Low-Rank Approximation

The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint.

Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.