Find determinant of $B=(A_1+A_{n-1}|A_2+A_{n}|A_3+A_1|A_4+A_2|...|A_n+A_{n-2})$ given $\det A$

Question

We have matrix $A \in \mathbb{R}^{n \times n}$ which we can write in columns form $A = (A_1|A_2|...|A_n)$, where $A_i$ is a column $i$.

Now, we make cyclic shift with a step 2 and add that to the old matrix and get a new matrix: $$B=(A_1+A_{n-1}|A_2+A_{n}|A_3+A_1|A_4+A_2|...|A_n+A_{n-2})$$

The task is to express $\det B$ in terms of $\det A$.

My attempt: I've tried to use linearity of determinant and decompose $\det B$ into $2^n$ terms. I know that a lot of the terms will be zero due to them having same columns, other non-zero terms are specific permutations which can be returned to $\det A$ by switching columns. But there are a lot of them and each one has it's own number of column shifts to return to $A$. So I am stuck here

 

Answer 1

Hint. Write $B=AC$ for some circulant matrix $C$. As there is an explicit formula for the determinant of a circulant matrix, you may calculate $\det(B)$ from $\det(A)$ and $\det(C)$.

Answer 2

There is a tricky way to get to the result, which is actually a bit articulated. Less tricky said, it is an elementary way to compute the determinant of the circulant matrix user1551 mentioned. We firstly see three lemmas, increasingly related to the problem.

Lemma 1. Suppose $\omega$ is a primitive $k$-th root of unity. Then $$\prod_{i=0}^{k-1}(1+\omega^i) = 1- (-1)^k$$

Proof. The solutions of the polynomial $x^k-1$ are the k-roots of unity, so that $$ x^k-1 = \prod_{i=0}^{k-1}(x-\omega^i) $$ Substituting $x=-1$ we get the desired result.

Lemma 2. Let $S$ be the $n \times n$ matrix such that $A (x_1, \ldots, x_n) = (x_n, x_1, \ldots, x_{n-1})$, i.e. the shift matrix. Then it is diagonalizable and its diagonal form is $\text{diag}(1, \omega, \ldots, \omega^{n-1})$, where $\omega$ is a primitive $n$ root of unity.

Proof. You can verify that the eigenvectors are $(1, \omega^j, \omega^{2j}, \ldots, \omega^{(k-1)j})$ for $j=0, \ldots, k-1$.

Lemma 3. Let $M$ be a matrix with diagonal form $D$. Then $$\det(1+M) =\det(1+D)$$

Proof. Indeed, let $B$ be such that $BMB^{-1} = D$. Multiplying $\det(1+M)$ by $\det(B), \det(B^{-1})$ we get $$ \det( B(1+M)B^{-1}) = \det(1+BMB^{-1}) = \det(1+D)$$

Okay! Here we are. Now the problem is almost done.

Let $A=(A_1 | \ldots | A_n)$ be a matrix. Note that $(A_{n-1}, A_n, A_1, \ldots, A_{n-2})$ can be written as $AS^2$. Indeed, when we multiply the two matrices we can do it row by row of A, getting the rows shifted by two: on balance, we'll have shifted the columns of $A$ by two.

You asked to compute $$\det(A+AS^2) = \det(A) \det(1+S^2)$$ By lemma 2, we know that the diagonal form of $S$ is $\text{diag}(1, \omega, \ldots, \omega^{n-1})$. Thus, the diagonal form of $S^2$ is $\text{diag}(1, \omega^2, \ldots, \omega^{2(n-1)})$. By Lemma 3, we are reduced to compute $$ \det(1+\text{diag}(1, \omega^2, \ldots, \omega^{2(n-1)}))$$

Because the exponents has to be reduced modulo n, we have distinguish $n$ even or odd.

Case 1: n odd. Here the numbers $2k$ spans all the numbers from 0 to $n-1$ (try $n=5$ to believe), so we compute $$ \det(1+\text{diag}(1, \omega, \ldots, \omega^{n-1})) = \prod_{k=0}^{n-1}(1+\omega^k) = 1-(-1)^n = 2$$ By lemma 1 and n odd.

** Case 2**: n even. Set $n=2m$. Here the numbers $2k$ spans twice the even numbers $0, 2,\ldots, 2(m-1)$ (try $n=6$ to believe), so we compute $$ \det(1+\text{diag}(1, \omega^2, \ldots, \omega^{2(m-1)},1, \omega^2, \ldots, \omega^{2(m-1)} )) = \left( \prod_{k=0}^{m-1}(1+(\omega^2)^k ) \right )^2 = (1-(-1)^m)^2 $$ Using the fact that $\omega^2$ is a primitive $m$-root of unity. We have two further cases: if $m$ is even the result is zero, otherwise is 4.

Conclusion On balance, the reuslt is the following (hard to guess a priori, in my opinion):

1. $2\det(A)$, if $n$ is odd;
2. $4\det(A)$, if $n$ is even but not multiple of four;
3. $0$, if $n$ is multiple of four.

You can have fun in computing the same thing for a general shift, depending on the gcd of the size and the shift (the same method applies!).