# Computing determinant of this matrix

I have a very specific kind of matrix and I have to find the formula to find the determinant of these matrix.

a(i,j)=a if(i==j) and a(i,j)=0 if(floor(i/2)=floor(j/2) and i!=j) and n is odd

$$A=(a_{i,j})_{n \times n}=\left( \begin{array}{ccccc} a&0&b&b \cdots &b&b\\ 0& a&b&b \cdots& b&b\\ b& b& a&0 \cdots& b&b\\ b& b& 0&a \cdots& b&b\\ \vdots& \vdots& \vdots& \ddots&\cdots\\ b&b&b & \cdots&b&a \end{array} \right)?$$

-
Try writing down its eigenvectors. – Qiaochu Yuan May 7 '13 at 9:50
What's the rule for the placement of the $0$'s ? – Raskolnikov May 7 '13 at 9:54
a(i,j)=a if(i==j) and a(i,j)=0 if(i/2=j/2 and i!=j) – Alen May 7 '13 at 9:59
Please notice n is odd – Alen May 7 '13 at 10:01

The problem is closely related to this one posted and answered yesterday, with $p\leftarrow2$, $np\leftarrow n-1$, $c\leftarrow a/b$, with the entire matrix divided by $b$.

Since according to a comment under the question $n$ is odd, we need to deal with the last component separately. All eigenvectors in the linked question except for the one filled with $1$s sum to $0$. Thus we can append a $0$ to them to obtain eigenvectors of the present matrix. That leaves a two-dimensional subspace to be dealt with, spanned by the vector $x$ that has a $1$ in the last component and the vector $y$ that has $1$s everywhere else. Applying $A$ to these vectors yields $Ax=ax+by$ and $Ay=(n-1)bx+((n-3)b+a)y$. Thus the product of the remaining two eigenvalues is

$$\left|\matrix{a&b\\(n-1)b&(n-3)b+a}\right|=((n-3)b+a)a-(n-1)b^2\;.$$

Multiplying this by the $n-2$ eigenvalues from the linked question, with the above substitutions and the factor $b^{n-2}$ that was divided out, yields the determinant of the present matrix:

\begin{align} \det A &= \left(((n-3)b+a)a-(n-1)b^2\right)b^{n-2}\left(\frac ab\right)^{(n-1)/2}\left(\frac ab-2\right)^{(n-3)/2} \\ &= \left(((n-3)b+a)a-(n-1)b^2\right)a^{(n-1)/2}\left(a-2b\right)^{(n-3)/2}\;. \end{align}

-
It sounds pretty close but $n$ is odd... – achille hui May 7 '13 at 11:38
@achille: Aha -- thanks for pointing that out -- yet another reminder why it's a bad idea to bury clarifications of the question deep in the comments... – joriki May 7 '13 at 11:42
Can this matrix have a particular formula? – Alen May 7 '13 at 11:58
@Alen: How do you mean, can it? – joriki May 7 '13 at 12:24
Means, can I derive a formula for calculating the det A? – Alen May 7 '13 at 12:33

Since $n$ is odd, let $n = 2m+1$ and $u_n$ be the $n \times 1$ column vector with all entries one.

The matrix $A$ can be rewritten to have the form $X + b u_n u_n^{T}$ where $X$ is a block diagonal matrix consists of $m$ $2\times 2$ block $\tilde{X}$ and one $1 \times 1$ block:

$$X = \begin{pmatrix} \tilde{X} & 0 & 0 & \dots & 0\\ 0 & \tilde{X} & 0 &\dots & 0\\ 0 & 0 & \tilde{X} &\dots & 0\\ \vdots &\vdots & \vdots & \ddots & 0\\ 0 & 0 & 0 & 0 & a - b \end{pmatrix} \quad\text{ and }\quad \tilde{X} = \begin{pmatrix}a - b & -b\\-b & a-b\end{pmatrix}$$

When one perturb an invertible matrix $X$ by a rank one matrix like $b u_n u_n^T$, it is known that the determinant of the updated matrix $X + b u_n u_n^{T}$ is given by:

$$\det( X + b u_n u_n^{T} ) = \det(X)( 1 + b u_n^{T} X^{-1} u_n )\tag{*}$$

Substitute our special form of $X$ into $(*)$ and notice:

\begin{align} \det(X) &= \det(\tilde{X})^m (a - b) = ((a-b)^2 - b^2)^m (a - b)\\ u_n^{T} X^{-1} u_n &= m\;u_2^T \tilde{X}^{-1} u_2 + \frac{1}{a-b} = \frac{2m}{a-2b} + \frac{1}{a-b} \end{align}

We get: \begin{align} \det A &= ((a-b)^2 - b^2)^m (a - b)\left\{1 + b \left(\frac{2m}{a-2b} + \frac{1}{a-b} \right)\right\}\\ &= a^m (a-2b)^{m-1}\left(a^2 + 2 (m-1)ab - 2mb^2\right) \end{align}

Update

For the general case when the matrix elements is given by:

$$a_{i,j} = \begin{cases} a, & \text{ for } i = j\\ 0, & \text{ for } \lfloor\frac{i}{q}\rfloor = \lfloor\frac{j}{q}\rfloor \wedge i \neq j\\ b, & \text{ otherwise }. \end{cases}$$

where $0 \le i, j < n$ and $q$ is an integer $> 1$. Let $n = mq + r$ where $0 \le r < q$. Once again, we rewrite $A$ into the form $X + b u_n u_n^T$ where X is now a block diagonal matrix consists of $m$ $q \times q$ block $\tilde{X}_q$ and one $r \times r$ block $\tilde{X}_r$.

It is not hard to verify the entries on $\tilde{X}_s$ is given by:

$$(\tilde{X}_s)_{i,j} = \begin{cases} a-b, &\text{ for } i = j\\-b, &\text{ otherwise. }\end{cases} \quad\implies\quad \begin{cases}\det(\tilde{X}_s) &= a^{s-1}(a - sb)\\ u_s^{T} \tilde{X}_s^{-1} u_s &= \frac{s}{a-sb}\end{cases}$$ Repeating the same procedure as above, we obtain the formula for $\det(A)$ in the general case:

$$\det A = (a^{q-1}(a - qb))^m (a^{r-1}(a-rb)) \left\{1 + b \left(\frac{mq}{a-qb} + \frac{r}{a-rb}\right)\right\}$$

-
hue:r can be -1 here? – Alen May 7 '13 at 16:44
@Alen that is a typo, should be $0 \le r < q$. In principle, one should treat $r = 0$ as a special case. However, it turns out the final expression also work for the $r = 0$ case. – achille hui May 7 '13 at 16:53
I was actually thinking of (pn-1)*(pn-1) dimension matrix – Alen May 7 '13 at 17:12
@Alen, your $pn-1$ case is equivalent to setting the parameters $(m,q,r)$ to $(n-1,p,p-1)$ in my answer. – achille hui May 7 '13 at 17:24