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](https://mathoverflow.net/questions/396525/how-quickly-can-irreducible-aperiodic-convex-combinations-of-permutation-matrice) and [this question](https://mathoverflow.net/questions/396352/convex-combinations-a-of-n-times-n-permutation-matrices-such-that-every-entr).



Factorizing the doubly stochastic matrix where all entries are equal such that the factors are all convex combinations of few permutation matrices
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}$.
> 
> 
> 


