# “Lift and project” procedure for matrices

Definition. Let us call $n\times n$ matrix with non-negative entries good if sum of every row and column is equal to $1/n$.

Suppose we have a good matrix $A$. Let us consider the following strange "lift and project" procedure. Let us consider $n \times n$ "matrix" $M$. I put "matrix" in quotes, because $M_{ij}$ is not a number - it is $n \times n$ matrix itself (again, with non-negative entries). We require the following conditions:

1. $\sum_{i,j} M_{ij} = A$
2. For every $i$ $\mathrm{rk}(\sum_j M_{ij}) = 1$
3. For every $j$ $\mathrm{rk}(\sum_i M_{ij}) = 1$
4. Let us define another matrix $B$. $B_{ij}$ is equal to the sum of all entries of $M_{ij}$. We require that $B$ is good.

I wonder if it is possible to characterize matrices $B$ that could be obtained via this procedure.

The original motivation is conditional independence of random variables.

• Why do you introduce a terminology ("good" matrix) for something which has already one ? Up to the factor $1/n$, a good matrix is nothing but a bi-stochastic matrix. – Denis Serre Dec 9 '10 at 16:09
• Though I agree with Denis Serre in principle, ;"good" is a lot easier to type; such re-naming seems quite common to me. – drbobmeister Dec 9 '10 at 17:17
• Denis Serre: yes, you are indeed right. I even hope that one can use decomposition of stochastic matrices into permutation matrices here somehow. – ilyaraz Dec 9 '10 at 17:26