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 problem about Determinant of sum of permutation matrices
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.


