12
$\begingroup$

Define

$ A=\begin{pmatrix} x_1 & x_2 & 0 & 0\\ 0 &1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{pmatrix}, B=\begin{pmatrix} 1 & 0 & 0 & 0\\ x_3 &x_4&x_5&0\\ 0&0&1&0\\ 0&0&0&1 \end{pmatrix}, C=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 &1&0&0\\ 0&x_6&x_7&x_8\\ 0&0&0&1 \end{pmatrix},$

$ D=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 &1&0&0\\ 0&0&1&0\\ 0&0&x_9&x_{10} \end{pmatrix}$.

Let $W$ be a product of above matrices. (For example $ W $ can be $D^2ABDC$ or $CAD$ (any product of above matrices)).

Now define reverse of $W$ as $Re(W)$. For example if $W=D^2ABDC$ then $Re(W)=CDBAD^2$, If $W=CAD$ then $Re(W)=DAC$.

I want to prove $\det(W+Re(W))-\det(W-Re(W))$ is divisible by $4$. In other words $\det(W+Re(W))-\det(W-Re(W))\equiv 0 \mod 4$.

Any comment really appreciated.

Note (Grumpy Parsnip): A generalized phenomenon seems to be true here. One can define $n\times n$ matrices of a similar form. E.g. $A_2=\left(\begin{array}{cc} x_1&x_2\\0&1\end{array}\right)$ and $B_2=\left(\begin{array}{cc} 1&0\\x_3&x_4\end{array}\right)$. Then it seems that for $2m\times 2m$ matrices,

$$\det(W+Re(W))+(-1)^{m-1}\det(W-Re(W))=0\mod 4.$$

Perhaps the $2\times 2$ case is easier to understand. I'll award a bounty for a solution to the $2\times 2$ case. (Hopefully the OP, who is a friend of mine, will not mind my edits.)

$\endgroup$
  • $\begingroup$ You want to prove that $4$ is a common factor of what and what? $\endgroup$ – Git Gud Jul 4 '14 at 21:01
  • $\begingroup$ Velcome to our site! You should however edit your post to make it less unclear what the question is. $\endgroup$ – kjetil b halvorsen Jul 4 '14 at 21:28
  • 1
    $\begingroup$ I assume you want $x_1,x_2,x_3...$ to be integers? $\endgroup$ – Cheerful Parsnip Jul 5 '14 at 0:38
  • 2
    $\begingroup$ OP shouldn't comment on the post anyway. OP should edit the post so it says what it's actually intended to say. $\endgroup$ – Gerry Myerson Jul 5 '14 at 12:34
  • 1
    $\begingroup$ @user90041: $Re(W)$ is defined as an operation on words, not on matrices. $\endgroup$ – Cheerful Parsnip Jul 13 '14 at 6:59
3
$\begingroup$

My impulse is to prove it by induction (on the number of factors in $W$). Clearly the result holds for any single-factor products. So, assuming that the result holds for $W$, show that $\det(AW+WA)\equiv \det(AW-WA)\mod 4$, and similarly for $B,C$, and $D$. Just doing the algebra by hand, I showed that it's true at least for $A$. I assume the others would work out somewhat similarly. At the very least, the calculation for $D$ would be symmetric.

$\endgroup$
  • 3
    $\begingroup$ Shouldn't you be considering $AW\pm Re(W)A$? $\endgroup$ – Cheerful Parsnip Jul 5 '14 at 17:49
  • $\begingroup$ Okay, I agree with you that for all matrices $W$, $\det(AW+WA)= \det(AW-WA)\mod 4$. I can't believe you did that by hand! I checked it using mathematica. $\endgroup$ – Cheerful Parsnip Jul 6 '14 at 8:01
  • $\begingroup$ But it's not obvious how this helps I guess. $\endgroup$ – Cheerful Parsnip Jul 6 '14 at 8:08
  • $\begingroup$ Isn't it? I mean, it seems like how you'd go about doing a proof by induction on the length of the product W. The idea is that if you can add any one of the four (I admit I only did the calculation for A) at a time, then the result holds for words of arbitrary length. $\endgroup$ – Keith Penrod Jul 10 '14 at 13:22
  • $\begingroup$ I did the calculation for all 4 and it works, but show me how that proves the result for $w=ABC$. $\endgroup$ – Cheerful Parsnip Jul 10 '14 at 17:27
3
+200
$\begingroup$

Added 2014-07-14: The Answer below is a rewrite of the former text which was essentially just an approach to a possible solution. It was based upon the idea to interpret the matrices $A_2$ and $B_2$ as transformation matrices for an automaton. The language which is generated by this automaton could then be analysed to find the solution.

Contrary to my first thoughts this approach is more cumbersome than proving the proposition by induction. So, with less insight to the problem, but also with less effort to provide a solution the answer below is based upon induction.


This is an answer referring to the note of Grumpy Parsnip. So, we put the focus on the $2\times2$-matrices

\begin{align*} A_2=\left( \begin{array}{cc} x_1 & x_2\\ 0 & 1 \end{array} \right) \qquad B_2=\left( \begin{array}{cc} 1 & 0\\ x_3 & x_4 \end{array} \right) \end{align*}

$A_2$ and $B_2$ are upper left sub-matrices of $A$ and $B$ of the original question. We assume integer entries and consider finite products of the above matrices $$W=\prod_{j=1}^{n}X_j\qquad X_j\in\{A_2,B_2\}$$ We define $Re(W) := \prod_{j=1}^{n}X_{n+1-j}$, a kind of reversed product and show:

The following statement valid:

\begin{align*} \det\left(W+Re(W)\right)+\det\left(W-Re(W)\right) \equiv 0(4)\tag{1} \end{align*}

Observe that we add in (1) the determinants corresponding to the factor $(-1)^{m-1}$ for $(2m\times2m)$-matrices of Grumpy Parsnips note.


Note: To illustrate the connection between the sub-matrices $A_2$ and $B_2$ and the matrices $A,B,C,D$ of the original question, see the picture with the corresponding automata below. The elements $x_{i,j}$ of a matrix are the labels of the edges from node $i$ to node $j$ of the automata. A matrix entry $1$ which is the neutral element with respect to multiplication is denoted with $\varepsilon$, the neutral element of concatenation of words of the formal language which are generated when walking along the edges of the automaton.

The automata clearly indicate the structural connection of the $(2\times 2)$ matrices $A_2,B_2$ and $(4\times 4)$ matrices $A,B,C,D$ making Grumpy Parsnips remark about generalisation of the matrices to $(2m\times 2m)$ matrices plausible, besides the factor $(-1)^{m-1}$ which was presumably a result of separate calculation.

enter image description here

[automata of transition matrices $A_2, B_2$ and $A,B,C,D$]


The following proof is done by induction on the number $n$ of factors of $W$

Induction base step $(n=1)$

In case $n=1$ we have to check two alternatives $W=A_2$ and $W=B_2$

Case $W=A_2$:

\begin{align*} \det&\left(A_2+Re(A_2)\right)+ \det\left(A_2-Re(A_2)\right)\\ &= \det(2\cdot A_2)+\det(0\cdot A_2)\\ &=2^2\det(A_2)\equiv 0(4) \end{align*}

Observe, that $Re(W)=Re(A_2)=A_2$.

Since the case $W=B_2$ is literally the same as $W=A_2$ the base step is proved.

Next, the

Induction hypotheses

We assume the statement $(1)$ is valid foreach $W=\prod_{j=1}^{n}X_j$ with $X_j\in\{A_2,B_2\}$.

So, let

\begin{align*} W=\left( \begin{array}{cc} w_{1,1} & w_{1,2}\\ w_{2,1} & w_{2,2} \end{array} \right) \qquad Re(W)=\left( \begin{array}{cc} w_{1,1}^\ast & w_{1,2}^\ast\\ w_{2,1}^\ast & w_{2,2}^\ast \end{array} \right) \end{align*}

Then we get

\begin{align*} \det&\left(W+Re(W)\right)+\det\left(W-Re(W)\right)\\ &=det\left( \begin{array}{cc} w_{1,1}+w_{1,1}^\ast & w_{1,2}+w_{1,2}^\ast\\ w_{2,1}+w_{2,1}^\ast & w_{2,2}+w_{2,2}^\ast \end{array} \right) +\det\left( \begin{array}{cc} w_{1,1}-w_{1,1}^\ast & w_{1,2}-w_{1,2}^\ast\\ w_{2,1}-w_{2,1}^\ast & w_{2,2}-w_{2,2}^\ast \end{array} \right)\\ &=(w_{1,1}+w_{1,1}^\ast)(w_{2,2}+w_{2,2}^\ast)-(w_{2,1}+w_{2,1}^\ast)(w_{1,2}+w_{1,2}^\ast)\\ &+(w_{1,1}-w_{1,1}^\ast)(w_{2,2}-w_{2,2}^\ast)-(w_{2,1}-w_{2,1}^\ast)(w_{1,2}-w_{1,2}^\ast)\\ &=2w_{1,1} w_{2,2}+2w_{1,1}^\ast w_{2,2}^\ast-2w_{1,2}w_{2,1}-2w_{1,2}^\ast w_{2,1}^\ast\\ &\equiv 0(4)\tag{2} \end{align*}

And now we show the

Induction step $(n \rightarrow n+1)$

We have to show that $(1)$ is valid for $WA_2$ and $WB_2$. It's sufficient to consider right multiplication with $A_2$ resp. $B_2$ since left multiplication is already subsumed by a proper choice of $W$.

Case $WA_2$:

\begin{align*} WA_2&=\left( \begin{array}{cc} w_{1,1} & w_{1,2}\\ w_{2,1} & w_{2,2} \end{array} \right)\left( \begin{array}{cc} x_1 & x_2\\ 0 & 1 \end{array} \right)\\ &=\left( \begin{array}{cc} w_{1,1}x_1 & w_{1,1}x_2+w_{1,2}\\ w_{2,1}x_1 & w_{2,1}x_2+w_{2,2} \end{array} \right)\\ A_2Re(W)&=\left( \begin{array}{cc} x_1 & x_2\\ 0 & 1 \end{array} \right)\left( \begin{array}{cc} w_{1,1}^\ast & w_{1,2}^\ast\\ w_{2,1}^\ast & w_{2,2}^\ast \end{array} \right)\\ &=\left( \begin{array}{cc} w_{1,1}^\ast x_1+w_{2,1}^\ast x_2 & w_{1,2}^\ast x_1+w_{2,2}^\ast x_2\\ w_{2,1}^\ast & w_{2,2}^\ast \end{array} \right) \end{align*}

So, we get

\begin{align*} \det&\left(WA_2+A_2Re(W)\right)+\det\left(WA_2-A_2Re(W)\right)\\ &=det\left( \begin{array}{cc} w_{1,1}x_1+w_{1,1}^\ast x_1+w_{2,1}^\ast x_2 & w_{1,1}x_2+w_{1,2}+w_{1,2}^\ast x_1+w_{2,2}^\ast x_2\\ w_{2,1}x_1+w_{2,1}^\ast & w_{2,1}x_2+w_{2,2}+w_{2,2}^\ast \end{array} \right)\\ &+det\left( \begin{array}{cc} w_{1,1}x_1-w_{1,1}^\ast x_1-w_{2,1}^\ast x_2 & w_{1,1}x_2+w_{1,2}-w_{1,2}^\ast x_1-w_{2,2}^\ast x_2\\ w_{2,1}x_1-w_{2,1}^\ast & w_{2,1}x_2+w_{2,2}-w_{2,2}^\ast \end{array} \right)\\ &=(w_{1,1}x_1+w_{1,1}^\ast x_1+w_{2,1}^\ast x_2)(w_{2,1}x_2+w_{2,2}+w_{2,2}^\ast)\\ &-(w_{2,1}x_1+w_{2,1}^\ast)(w_{1,1}x_2+w_{1,2}+w_{1,2}^\ast x_1+w_{2,2}^\ast x_2)\\ &+(w_{1,1}x_1-w_{1,1}^\ast x_1-w_{2,1}^\ast x_2)(w_{2,1}x_2+w_{2,2}-w_{2,2}^\ast)\\ &-(w_{2,1}x_1-w_{2,1}^\ast)(w_{1,1}x_2+w_{1,2}-w_{1,2}^\ast x_1-w_{2,2}^\ast x_2)\\ &=(2w_{1,1} w_{2,2}+2w_{1,1}^\ast w_{2,2}^\ast-2w_{1,2}w_{2,1}-2w_{1,2}^\ast w_{2,1}^\ast)x_1\\ &\equiv 0(4) \end{align*}

according to the induction hypothesis $(2)$.

Case $WB_2$:

\begin{align*} WB_2&=\left( \begin{array}{cc} w_{1,1} & w_{1,2}\\ w_{2,1} & w_{2,2} \end{array} \right)\left( \begin{array}{cc} 1 & 0\\ x_3 & x_4 \end{array} \right)\\ &=\left( \begin{array}{cc} w_{1,1}+w_{1,2}x_3 & w_{1,2}x_4\\ w_{2,1}+w_{2,2}x_3 & w_{2,2}x_4 \end{array} \right)\\ B_2Re(W)&=\left( \begin{array}{cc} 1 & 0\\ x_3 & x_4 \end{array} \right)\left( \begin{array}{cc} w_{1,1}^\ast & w_{1,2}^\ast\\ w_{2,1}^\ast & w_{2,2}^\ast \end{array} \right)\\ &=\left( \begin{array}{cc} w_{1,1}^\ast & w_{1,2}^\ast\\ w_{1,1}^\ast x_3+w_{2,1}^\ast x_4 & w_{1,2}^\ast x_3+w_{2,2}^\ast x_4 \end{array} \right) \end{align*}

So, we get

\begin{align*} \det&\left(WB_2+B_2Re(W)\right)+\det\left(WB_2-B_2Re(W)\right)\\ &=det\left( \begin{array}{cc} w_{1,1}+w_{1,2}x_3+w_{1,1}^\ast & w_{1,2}x_4+w_{1,2}^\ast\\ w_{2,1}+w_{2,2}x_3+w_{1,1}^\ast x_3+w_{2,1}^\ast x_4 & w_{2,2}x_4+w_{1,2}^\ast x_3+w_{2,2}^\ast x_4 \end{array} \right)\\ &+det\left( \begin{array}{cc} w_{1,1}+w_{1,2}x_3-w_{1,1}^\ast & w_{1,2}x_4-w_{1,2}^\ast\\ w_{2,1}+w_{2,2}x_3-w_{1,1}^\ast x_3-w_{2,1}^\ast x_4 & w_{2,2}x_4-w_{1,2}^\ast x_3-w_{2,2}^\ast x_4 \end{array} \right)\\ &=(w_{1,1}+w_{1,2}x_3+w_{1,1}^\ast)(w_{2,2}x_4+w_{1,2}^\ast x_3+w_{2,2}^\ast x_4)\\ &-(w_{2,1}+w_{2,2}x_3+w_{1,1}^\ast x_3+w_{2,1}^\ast x_4)(w_{1,2}x_4+w_{1,2}^\ast)\\ &+(w_{1,1}+w_{1,2}x_3-w_{1,1}^\ast)(w_{2,2}x_4-w_{1,2}^\ast x_3-w_{2,2}^\ast x_4)\\ &-(w_{2,1}+w_{2,2}x_3-w_{1,1}^\ast x_3-w_{2,1}^\ast x_4)(w_{1,2}x_4-w_{1,2}^\ast)\\ &=(2w_{1,1} w_{2,2}+2w_{1,1}^\ast w_{2,2}^\ast-2w_{1,2}w_{2,1}-2w_{1,2}^\ast w_{2,1}^\ast)x_4\\ &\equiv 0(4) \end{align*}

according to the induction hypothesis $(2)$ which completes the proof by induction.


Note: A proof by induction of the original answer could be done in the same way (with considerably more effort :-) )

$\endgroup$
  • $\begingroup$ thanks for the answer. Your counterexample in the 2 by 2 case is to a different problem! In that case, the conjecture is that the sum of the two determinants is a multiple of four, not the difference. $\endgroup$ – Cheerful Parsnip Jul 13 '14 at 2:52
  • $\begingroup$ I still need to read through the rest, but it looks nice, and you clearly put a lot of effort into it.! $\endgroup$ – Cheerful Parsnip Jul 13 '14 at 2:53
  • $\begingroup$ @GrumpyParsnip: Ah, yes you're right! These are good news! :-) So, I can try to proceed with the proof. I will do it within the next few days and then I correct my answer. Best regards. $\endgroup$ – Markus Scheuer Jul 13 '14 at 6:13
  • $\begingroup$ Since, the bounty expires in a few hours, I am awarding it to you. Hopefully this doesn't lessen your diligence in searching for a proof. :) $\endgroup$ – Cheerful Parsnip Jul 13 '14 at 7:00
  • $\begingroup$ @GrumpyParsnip: First of all thanks for the bounty and of course I'm working on a solution (I like small challenges :-)) Currently I have a partial solution for the easy stuff. Please expect an update next weekend. $\endgroup$ – Markus Scheuer Jul 13 '14 at 21:19

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.