# A problem about Determinant of sum of permutation matrices

Let $w_1$ and $w_2$ be two permutations of $\{1, \cdots , k\}$ such that for all $1\leq i \leq k$, $w_1(i)\neq w_2(i)$. Let $m$ and $n$ be two relatively prime integers. Then is there exist two diagonal matrices $D_1, D_2 \in M_k(\mathbb{Z})$, with $\gcd(\text{det}D_1, n)=1$, $\gcd(\text{det}D_2, m)=1$ such that $\text{det}\big(D_1m(w_1I) + D_2n(w_2I)\big)=1$.

Here $\text{det}$ stands for determinant and $I$ is a $k\times k$ identity matrix. $w_iI$ is the permutation matrix corresponding to $w_i$.

-
Is $(w_1I)$ the permutation matrix of $w_1$? – Peter Mueller Jul 19 '13 at 17:21
Where does this question come from? – Igor Rivin Jul 19 '13 at 19:31
Does diagonal matrix mean constant diagonal? Or are different elements allowed on the diagonal? – The Masked Avenger Jul 19 '13 at 21:26
@PeterMueller yes, $(w_1I)$ is the permutation matrix of the identity matrix $I$. – Kamalakshya Jul 20 '13 at 3:32
@IgorRivin, This question came while writing a proof of a theorem, as an intermediate step. But the context of the theorem is quite unrelated. – Kamalakshya Jul 20 '13 at 3:36

I think Igor Rivin's original answer is correct, and that no hypothesis of $w_1(i) \neq w_2(i)$ is needed, nor do I see the subtlety he refers to in his recent edit. I'm writing this out in full so people can point out whether I missed anything.

First of all $$\det( m D_1 w_1 + n D_2 w_2 ) = \pm \det(m D_1 + n D_2 (w_2 w_1^{-1}) ).$$ Set $u = w_2 w_1^{-1}$.

Break $m D_1 + n D_2 u$ into blocks according to the cycle structure of $u$. In other words, $u$ permutes the rows and columns of each block cyclically. Each block looks like $$\begin{pmatrix} m a_1 & n b_1 & 0 & 0 & \cdots & 0 \\ 0 & m a_2 & n b_2 & 0 & \cdots & 0 \\ 0 & 0 & m a_3 & n b_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & m a_k & n b_k \\ n b_k & 0 & \cdots & 0 & 0 & m a_k \\ \end{pmatrix}$$ and thus has determinant $m^k \prod a_i \pm n^k \prod b_i$. Our job is to choose the $a$'s and $b$'s.

If $GCD(m^k, n^k) =1$ then there exist $A$ and $B$ with $A m^k + B n^k=1$. We necessarily have $GCD(A,n)=1$ and $GCD(B,m)=1$. Choose the $a_i$ and $b_i$ to have product $A$ and $B$ and fiddle with the signs as necessary.

-
Onething to observe here that to construct $D_1$ and $D_2$ , we just need the cycle lenghts of $w_2w_1^{-1}$ and a representative for each cycle. – Kamalakshya Aug 5 '13 at 3:39

I strongly believe this question is homework, but here is a sketch of the argument: By precomposing with $w_1^{-1}$ we can assume that one of the permutations is the identity and the second ($w_2$) is a derangement. Now, decompose $w_2$ into cycles; without loss of generality, the cycles are of the form $(1, \dots, n_1), (n_1+1, \dots, n_2), \dots),$ Now one needs to compute the determinant of a sum of a diagonal matrix $D_1$ and a cyclic permutation of a diagonal matrix. It is easy to see that this is the sum or the difference of the determinants (compute the eigenvectors, then multiply the corresponding eigenvalues). Now the assertion follows easily.

EDIT I am adding the edit because it occurred to me that the question is slightly more subtle than is apparent at first glance.

As indicated, normalize so that the first permutation is the identity, and then try to find an eigenvector $v$ for eigenvalue $\lambda.$ In each coordinate we have:

$$a_i v_i + b_i v_{\sigma(i)} = \lambda v_i,$$ so we have

$$\frac{\lambda-a_i}{b_i} = \frac{v_{\sigma_i}}{v_i}.$$

Multiplying the left hand sides and the right hand sides over all $i,$ and using the fact that $\sigma$ is a permutation, we get. $$\prod_i(\lambda-a_i) = \prod_i b_i,$$ so $\lambda$ satisfies an equation of degree $n$ whose constant term is $\prod_i b_i + (-1)^{n+1} \prod a_i,$ and the two products are exactly the determinants of the two matrices.

All good, BUT a sharp-eyed reader will have noted that we have divided by $v_i,$ which could well be zero. It can't be if $\sigma$ is transitive (so, a cycle), since then $v_{\sigma(i)}$ will be zero, and our alleged eigenvector is the zero vector, which is not possible, but it can be if $\sigma$ is not transitive, and indeed, if two of the cycles happen to have the same eigenvalue, we can combine the eigenvectors, filling in by zeros for the other cycles (actually, we can just take ONE cycle and its eigenvalue/eigenvector and fill in by zeros elsewhere). So the upshot is that the answer to the OP's original question is YES if $\sigma$ is a cycle, but NO in general without further hypotheses on the $a_i, b_i.$

-
Still I did not get the proof. Here the problem is diagonal matrices do not commute with permutation matrices. – Kamalakshya Jul 20 '13 at 7:04
That is not used in the argument – Igor Rivin Jul 20 '13 at 20:51
I don't see any subtlety here. I wrote out below what I take to be your argument. (I hope I haven't solved a homework question here, but I thought it looked more like the kind of thing that comes up when reducing a problem in some other area to combinatorics, and not thinking very hard about the result.) – David Speyer Jul 22 '13 at 17:35