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