Factorizing the doubly stochastic matrix where all entries are equal such that the factors are all convex combinations of few permutation matrices

Question

Let $N_{n}=(1/n)_{i=1,j=1}^{n}$ be the $n\times n$-matrix where all the entries are equal.

Suppose $n>0$. Let $\delta_{n}$ be the least natural number such that $N_{n}$ can be factored as $N_{n}=A_{1}\dots A_{k}$ for some $k$ and $A_{1},\dots,A_{k}$ such that if $1\leq i\leq k$, then $A_{i}$ is the convex combination of at most $\delta_{n}$ many permutation matrices. Is $\delta_{n}=2$ for all $n>1$? If not, then what are the constants $\delta_{n}$? If $\delta_{n}$ is difficult to calculate exactly, what are some upper or lower bounds on the constants $\delta_{n}$?

Observe that $\delta_{n}\leq n$ since $N_{n}$ is the convex combination of $n$ permutation matrices.

Lemma: $\delta_{a_{1}\dots a_{r}}\leq\max(\delta_{a_{1}},\dots,\delta_{a_{r}})$.

Proof: Suppose that $N_{a_{i}}=A_{i,1}\dots A_{i,k}$ where each $A_{i,j}$ is the convex combination of at most $\delta_{a_{i}}$ many permutation matrices.

$$N_{n}=N_{a_{1}}\otimes\dots\otimes N_{a_{r}}$$ $$=(N_{a_{1}}\otimes I_{a_{2}\dots a_{r}})(I_{a_{1}}\otimes N_{a_{2}}\otimes I_{a_{3}\dots a_{r}})\dots(I_{a_{1}\dots a_{r-1}}\otimes N_{a_{r}}).$$

However, for $1\leq i\leq r$, we have $$I_{a_{1}\dots a_{i-1}}\otimes N_{a_{i}}\otimes I_{a_{i+1}\dots a_{r}}= (I_{a_{1}\dots a_{i-1}}\otimes A_{i,1}\otimes I_{a_{i+1}\dots a_{r}})\dots (I_{a_{1}\dots a_{i-1}}\otimes A_{i,k}\otimes I_{a_{i+1}\dots a_{r}}).$$

Q.E.D.

As a consequence, we conclude that $\delta_{n}\leq p$ whenever $n>1$ and $p$ is the largest factor of $n$. However, I have shown that $\delta_{3}=2$ experimentally, so the reverse inequality does not always hold.

This is a continuation of the series of questions including this question and this question.

Answer 1

I claim that $\delta_{n}=2$ for all $n$.

Lemma: For each $n$, and each vector $[x_{1},\dots,x_{n}]^{T}$ with $x_{1}+\dots+x_{n}=0$, there are matrices $A_{1},\dots,A_{k}$ where each $A_{i}$ is the convex combination of $2$ permutation matrices and where $A_{1}\dots A_{k}[x_{1},\dots,x_{n}]^{T}=\mathbf{0}$.

Proof: Let $r$ be the number of non-zero entries in the vector $[x_{1},\dots,x_{n}]^{T}$. Then we shall prove this result by induction on $r$. The result is clear when $r=0,r=1$, so assume $r>1$. Then there is a permutation matrix $A$ such that $A[x_{1},\dots,x_{n}]^{T}=[y_{1},\dots,y_{r-1},y_{r},0,\dots,0]^{T}$ such that $y_{r-1}>0,y_{r}<0$.

Let $t=\frac{y_{r-1}}{y_{r-1}-y_{r}}$.

Then $$(t\cdot I_{n}+(1-t)\cdot\rho_{(r-1,r)})[y_{1},\dots,y_{r-1},y_{r},0,\dots,0]^{T}$$ $$=t[y_{1},\dots,y_{r-1},y_{r},0,\dots,0]^{T}+(1-t)[y_{1},\dots,y_{r-2},y_{r},y_{r-1},0,\dots,0]^{T}=[y_{1},\dots,y_{r-2},y_{r-1}+y_{r},0,\dots,0]^{T}.$$ Therefore, there are matrices $A_{1},\dots,A_{k}$ where $$A_{1}\dots A_{k}[y_{1},\dots,y_{r-2},y_{r-1}+y_{r},0,\dots,0]^{T}=\mathbf{0}$$ and $A_{i}$ is the convex combination of 2 permutation matrices for $1\leq i\leq k$. Therefore, if we set $A_{k+1}=t\cdot I_{n}+(1-t)\cdot\rho_{(r-1,r)}$ and $A_{k+2}=A$, then $A_{1}\dots A_{k+2}[x_{1},\dots,x_{n}]^{T}=\mathbf{0}$ and $A_{i}$ is the convex combination of 2 permutation matrices whenever $1\leq i\leq k+2$. Q.E.D.

Theorem: For all $n>1$, we have $N_{n}=A_{1}\dots A_{k}$ for some $k$ and matrices $A_{1},\dots,A_{k}$ such that $A_{i}$ is the convex combination of $2$ permutation matrices for $1\leq i\leq k$.

Proof: Observe that if $A$ is a doubly stochastic matrix, then $A=N_{n}$ if and only if $A(x_{1},\dots,x_{n})^{T}=\mathbf{0}$ whenever $x_{1},\dots,x_{n}$ are real numbers with $x_{1}+\dots+x_{n}=0$.

Let $V$ be the space of all column vectors $[x_{1},\dots,x_{n}]^{T}$ with $x_{1}+\dots+x_{n}=0$.

Claim: For all $r$ with $0\leq r<n$, there are matrices $A_{1}\dots A_{k}$ where for $1\leq i\leq k$, the matrix $A_{i}$ is the convex combination of two permutation matrices and where $\text{dim}(V\cap\text{null}(A))\geq r$ where $A=A_{1}\dots A_{k}$.

Proof: We prove this claim by induction on $r$. The case when $r=0$ is trivial. Suppose now that $A=A_{1}\dots A_{k}$ where $\text{dim}(V\cap\text{null}(A))\geq r$ and where $A_{i}$ is the convex combination of two $n\times n$ permutation matrices for $1\leq i\leq r$. Now, if $\dim(V\cap\text{null}(A))=n-1$, then the induction step is complete. If $\dim(V\cap\text{null}(A))<n-1$, then let $[x_{1},\dots,x_{n}]^{T}\in V\setminus\text{null}(A)$, and let $[y_{1},\dots,y_{n}]^{T}=A[x_{1},\dots,x_{n}]^{T}$. Then there are matrices $A_{-r}\dots A_{0}$ such that $A_{-r}\dots A_{0}[y_{1},\dots,y_{n}]^{T}$ and $A_{i}$ is the convex combination of two permutation matrices for $-r\leq i\leq 0$. Therefore, if $B=A_{-r}\dots A_{0}A_{1}\dots A_{k}$, then $\dim(V\cap\text{null}(B))\geq r+1$. Our claim has been proven.

The result follows from our claim in the case that $r=n-1$. Q.E.D.

We are in fact able to produce the following explicit factorization of $N_{n}$

Let $$C_{n,r}=\frac{1}{r+1}(I_{n}+r\rho_{(r,r+1)}).$$ Let $$D_{n,r}=C_{n,1}\dots C_{n,r-1}.$$

Theorem: Suppose $n>0$. Then $N_{n}=D_{n,n}\dots D_{n,2}.$

Proof outline: We use induction. Using the induction hypothesis, we have $$D_{n,n-1}\dots D_{n,2}=\begin{bmatrix}N_{n-1} & \mathbf{0}\\ \mathbf{0}&I_{1} \end{bmatrix}.$$

Set $A=D_{n,n-1}\dots D_{n,2}$. Then $\dim(\ker(A)\cap V)=n-2$. Now, $[-1,\dots,-1,n-1]^{T}\in V\setminus\ker(A)$, however, $$D_{n,n-1}A[-1,\dots,-1,n-1]^{T}=D_{n,n-1}[-1,\dots,-1,n-1]^{T}=\mathbf{0},$$ so $\dim(\ker(D_{n,n-1}A)\cap V)>n-2$, but this is only possible if $V\subseteq\ker(D_{n,n-1}A)$. This implies that $D_{n,n-1}A=N_{n}$. Q.E.D.

There are other decompositions as well.

Theorem: Suppose $n>0$. Then $D_{n,n}^{n-1}=N_{n}$.