4
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – loop Nov 12 '17 at 20:18
  • $\begingroup$ @loop Sorry, I forgot a power. $\endgroup$ – Ian Nov 12 '17 at 20:34
  • $\begingroup$ 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? $\endgroup$ – loop Nov 12 '17 at 21:12
  • $\begingroup$ @loop Oh I'm dumb, it isn't additive like that. Hold on, let me figure out how to fix that... $\endgroup$ – Ian Nov 12 '17 at 21:28
  • 1
    $\begingroup$ @loop I came up with a much less comprehensive answer, but it does give you a sufficient condition. $\endgroup$ – Ian Nov 12 '17 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.