talk/dsscintuition.tex~

   1 \begin{block}{From Theory}
   2 Find all the $2^n\times 2^n$ matrices $\dfrac{1}{n}.M$ such that:
   3 \begin{enumerate}
   4 \item $M_{ij}=0$ if $j$ is not a neighbor of $i$
   5 %, \textit{i.e.},  there is no edge from $i$ to $j$ in the $n$-cube.
   6 \item $0 \le M_{ii} \le n$: the number of loops around $i$ is lesser than $n$
   7 \item Otherwise $M_{ij}=1$ if the edge from $i$ to $j$ is kept and 0 otherwise
   8 \item For any index of line $i$, $1 \le i\le 2^n$, $n = \sum_{1 \le j\le 2^n} M_{ij}$:
   9   the matrix is right stochastic
  10 \item For any index of column $j$,
  11   $1 \le j\le 2^n$, $n = \sum_{1 \le i\le 2^n} M_{ij}$:
  12   the matrix is left stochastic
  13 \item All the values of $\sum_{1\le k\le 2^n}M^k$ are strictly positive, (the induced graph is strongly connected)
  14 \end{enumerate}
  15 \end{block}
  16
  17
  18