3
$\begingroup$

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

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

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Aug 5, 2013 at 3:39
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Still I did not get the proof. Here the problem is diagonal matrices do not commute with permutation matrices. $\endgroup$ Jul 20, 2013 at 7:04
  • $\begingroup$ That is not used in the argument $\endgroup$
    – Igor Rivin
    Jul 20, 2013 at 20:51
  • $\begingroup$ 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.) $\endgroup$ Jul 22, 2013 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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