Quasi-Toeplitz row-equivalence conjecture

A dimension obstruction in every sufficiently large dimension

The conjecture is false. More precisely, whenever

$$r(n-r)>2n-2,$$

a Zariski-open dense family of rank-$r$ complex $n\times n$ matrices is not row equivalent to any quasi-Toeplitz matrix.

Index rows and columns by $0,\ldots,n-1$. A Toeplitz matrix has the form

$$T(t)_{ij}=t_{j-i}, \qquad -(n-1)\leq j-i\leq n-1.$$

Its $2n-1$ diagonal parameters determine a point

$$[t_{-(n-1)}:\cdots:t_{n-1}]\in\mathbb P^{2n-2},$$

because simultaneous multiplication of all parameters by a nonzero scalar does not change any row space.

Fix an $r$-element subset $I\subseteq\{0,\ldots,n-1\}$. On the open set where the rows indexed by $I$ are linearly independent, there is a rational map

$$\begin{aligned} \phi_I:\mathbb P^{2n-2}&\dashrightarrow\operatorname{Gr}(r,n),\\ [t]&\longmapsto \operatorname{span}\{(t_{-i},t_{1-i},\ldots,t_{n-1-i}):i\in I\}. \end{aligned}$$

Therefore its image closure satisfies

$$\dim\overline{\operatorname{im}(\phi_I)}\leq 2n-2.$$

Suppose a rank-$r$ quasi-Toeplitz matrix is obtained from $T(t)$ by replacing some rows with zero rows. Even if more than $r$ nonzero rows remain, one can choose $r$ linearly independent retained rows. Their index set $I$ satisfies

$$\operatorname{row}(Q)=\phi_I([t]).$$

Thus all row spaces attainable by rank-$r$ quasi-Toeplitz matrices belong to

$$\mathcal Z_{n,r} =\bigcup_{\substack{I\subseteq\{0,\ldots,n-1\}\\|I|=r}} \overline{\operatorname{im}(\phi_I)}.$$

The Grassmannian is irreducible and has dimension

$$\dim\operatorname{Gr}(r,n)=r(n-r).$$

When $r(n-r)>2n-2$, every set in the finite union defining $\mathcal Z_{n,r}$ is a proper closed subset. Hence

$$\mathcal Z_{n,r}\subsetneq\operatorname{Gr}(r,n), \qquad \operatorname{codim}(\mathcal Z_{n,r}) \geq r(n-r)-(2n-2)>0.$$

Choose any $r$-plane outside this union and form an $n\times n$ matrix whose first $r$ rows are a basis for that plane and whose remaining rows vanish. Row equivalence preserves and is characterized by the row space, so this matrix cannot be row equivalent to any quasi-Toeplitz matrix.

In particular,

$$n=8,\qquad r=4,\qquad \dim\operatorname{Gr}(4,8)=16>14=\dim\mathbb P^{14}.$$

The obstruction occurs in every dimension $n\geq8$: taking $r=\lfloor n/2\rfloor$ gives

$$\left\lfloor\frac{n^2}{4}\right\rfloor>2n-2 \qquad(n\geq8).$$

Since the construction is defined over $\mathbb Q$ and rational points are Zariski dense in the standard affine Grassmannian chart, rational, and hence integer, counterexamples also exist in every such dimension.

An explicit binary counterexample of order eight

In fact, the following matrix already has entries only in $\{0,1\}$:

$$A= \begin{pmatrix} 1&0&0&0&1&1&1&1\\ 0&1&0&0&1&0&0&0\\ 0&0&1&0&1&0&1&1\\ 0&0&0&1&1&0&1&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0 \end{pmatrix}.$$

Its rank is four. Write

$$C= \begin{pmatrix} 1&1&1&1\\ 1&0&0&0\\ 1&0&1&1\\ 1&0&1&0 \end{pmatrix}, \qquad U=\operatorname{row}(A)=\operatorname{row}(I_4\mid C).$$

A vector $y\in\mathbb C^8$ belongs to $U$ precisely when

$$y_{4+k}=\sum_{j=0}^{3}C_{jk}y_j \qquad(0\leq k\leq3).$$

Consequently, for a four-element row-index set $I$, the selected rows of a Toeplitz matrix belong to $U$ precisely when its diagonal parameters satisfy

$$t_{4+k-i}-\sum_{j=0}^{3}C_{jk}t_{j-i}=0 \qquad(i\in I,\ 0\leq k\leq3).$$

Let $L_I$ denote this integer coefficient matrix. Its $16$ equations involve exactly

$$w_I=8+\max I-\min I$$

diagonal parameters. Direct row reduction modulo $5$ gives the following complete census of the $\binom84=70$ index sets:

$$\begin{array}{c|c|c|c|c} \max I-\min I&w_I&\operatorname{rank}_{\mathbb F_5}(L_I) &\dim\ker_{\mathbb F_5}(L_I)&\#I\\ 3&11&11&0&5\\ 4&12&12&0&12\\ 5&13&13&0&18\\ 6&14&14&0&20\\ 7&15&15&0&13\\ 7&15&14&1&2 \end{array}$$

For the first $68$ index sets, full column rank modulo $5$ implies full column rank over $\mathbb C$. Therefore their only possible diagonal parameters are zero, and the selected Toeplitz rows cannot span $U$.

The remaining two index sets are

$$I_1=\{0,1,2,7\}, \qquad I_2=\{0,5,6,7\}.$$

In the diagonal order $t_{-7},\ldots,t_7$, their complex kernels are respectively spanned by

$$q_1=(0,1,0,0,1,0,0,0,0,0,0,0,0,0,0),$$

and

$$q_2=(0,0,0,0,0,0,0,0,0,0,1,1,0,1,0).$$

Indeed, each displayed integer vector solves the corresponding equations, while the modular rank $14$ proves that the complex kernel has dimension exactly one. For $I_1$, the rows indexed by $0,1,2$ vanish, and the only nonzero selected row is

$$T(q_1)_{7,*}=(0,1,0,0,1,0,0,0).$$

For $I_2$, the rows indexed by $5,6,7$ vanish, and the only nonzero selected row is

$$T(q_2)_{0,*}=(0,0,0,1,1,0,1,0).$$

In both exceptional cases, the selected rows have rank one instead of four. Therefore no four independent rows of any Toeplitz matrix lie in $U$, and the binary matrix $A$ is not row equivalent to any quasi-Toeplitz matrix.

The statement disproved here is Conjecture 5.2 of Ignacio García-Marco, Irene Márquez-Corbella, and Daniel Seco, On the minimum number of Toeplitz factors of a matrix, https://arxiv.org/abs/2506.16432. The distinct factorization conjectures in that paper are not asserted here.