# Conditions for the invertibility of doubly stochastic matrix

I am trying to find conditions for the invertibility of the matrix resulting from the convex combination of all possible permutation matrices of dimension $n \times n$ (to put it in context, and in case it helps, each of the permutation matrices identifies a different order in which an agent would rank n distinct alternatives), where:

• a permutation matrix is a square matrix for which each column/row has exactly one element equal to 1, and takes value zero elsewhere.
• a doubly stochastic matrix is a square matrix of non negative real numbers for which the row sum and the column sum is equal to 1
• a convex combination is a linear combination whose coefficients add up to 1

So for instance for $n=3$ the object of study would be: $$\tau_{1}\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{array}\right]+\tau_{2}\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{array}\right]+\tau_{3}\left[\begin{array}{ccc} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{array}\right]+\tau_{4}\left[\begin{array}{ccc} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{array}\right]+\tau_{5}\left[\begin{array}{ccc} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{array}\right]+\tau_{6}\left[\begin{array}{ccc} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0 \end{array}\right] = \left[\begin{array}{ccc} \tau_1+\tau_2 & \tau_3+\tau_4 & \tau_5+\tau_6\\ \tau_3+\tau_5 & \tau_1+\tau_6 & \tau_2+\tau_4\\ \tau_4+\tau_6 & \tau_2+\tau_5 & \tau_1+\tau_3 \end{array}\right]$$ where $\sum_{i=1}^{6}\tau_{i}=1$ and $\tau_{i}\geq0$ for all $i=1,...,6$.

Of course I am looking for answers in the case of generic $n$.

Even conditions under which the resulting matrix is non-singular for a finite number of values would still do it for me.

Is there a standard reference for this? I could not find any, but as I am not a mathematician I suspect it may be something really obvious that is dealt with e.g. in problem sets.

Thank you!

A simple condition for invertibility is strict diagonal dominance. In this case, changing notation so that you have $\tau_0,\tau_1,\dots,\tau_{n!-1}$ multiplying $P_0,\dots,P_{n!-1}$ with $P_0=I$, that condition reads $\tau_0>\sum_{i=1}^{n!-1} \tau_i$. This condition can be relaxed to allow you to arbitrarily permute rows; thus it is also sufficient to have any given $i$ with $\tau_i>\sum_{j \in \{ 0,1,\dots,n!-1 \},j \neq i} \tau_j$.
This criterion is not at all comprehensive, but it does give you a decent-sized family of cases to work with. There are also non-invertible cases like $\begin{bmatrix} 1/2 & 1/2 \\ 1/2 & 1/2 \end{bmatrix}$ which are "right on the boundary" i.e. they have an $i$ with $\tau_i=\sum_{j \in \{ 0,1,\dots,n!-1 \},j \neq i} \tau_j$.
• Thank you Ian, but either I do not understand you, or it does not work. E.g. your anwer applied to the example above would yield as determinant $\tau_{1}+\tau_{4}+\tau _{5}-\left( \tau_{2}+\tau_{3}+\tau_{6}\right)$, whereas for that case the determinant is different - to avoid writing the long expression, take eg $\tau=\left[ \frac{1}{6},\frac{1}{3},\frac{1}{12},\frac{1}{12},\frac{5}{24},\frac{1}{8}\right]$. The determinant is $-\frac{1}{24}$, while your calculation would yield $-\frac{1}{3}$. – loop Nov 12 '17 at 20:18
• thank you, but still I am not sure - again with the example the determinant of $$\left[ \begin{array} [c]{ccc} \frac{1}{2} & \frac{1}{6} & \frac{1}{3}\\ \frac{7}{24} & \frac{7}{24} & \frac{5}{12}\\ \frac{5}{24} & \frac{13}{24} & \frac{1}{4} \end{array} \right]$$ your formula yields $\left( \left( \frac{1}{6}\right) ^{3}+\left( \frac{1}{12}\right) ^{3}+\left( \frac{1}{12}\right) ^{3}\right) -\left( \left( \frac{1}{3}\right) ^{3}+\left( \frac{5}{24}\right) ^{3}+\left( \frac{1}{8}\right) ^{3}\right) = -\frac{73}{1728}\neq -\frac{1}{3}$, no? – loop Nov 12 '17 at 21:12