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$.