# Triadiagonal Symmetric Positive Definite matrix show that $B_N = C_N C_N^T$

I am given a matrix $N$ × $N$ symmetric positive definite matrix $B_N$

$$B_N = \begin{bmatrix} 2 & -1 & 0 & 0 & \cdots & \cdots\\ -1 & 2 & -1 & 0 & \cdots & \cdots\\ \vdots & \vdots & \ddots & \cdots & \cdots & \cdots \\ \vdots & \vdots & \vdots & \ddots & \cdots & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots & -1 \\ \vdots & \vdots & \vdots & \vdots & -1 & 2 \\ \end{bmatrix}$$

$C_N$ is a $N \times (N+1)$ matrix with entries equal to $1$ on the main diagonal and equal to $−1$ on the upper diagonal, and with all the other entries equal to $0$ i.e.

$$C_N = \begin{bmatrix} 1 & -1 & 0 & 0 & \cdots & \cdots & \cdots\\ 0 & 1 & -1 & 0 & \cdots & \cdots & \cdots\\ 0 & 0 & 1 & -1 & \cdots & \cdots & \cdots\\ \vdots & \vdots & \vdots & \ddots & \cdots & \cdots & \cdots\\ \vdots & \vdots & \vdots & \vdots & \ddots & -1 & \cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots & 1 & -1 \end{bmatrix}$$

I have to show that $B_N = C_N C_N^T$.

I am badly stuck. Any idea how to approach this question.

-
I rewrote the entire question. Kindly use $\LaTeX$ in the future. What have you tried so far? All you need to do is just matrix matrix multiplication. – user17762 Mar 14 '12 at 18:51
Thanks Sivaram. So far I am able to show that A(i,i) is 2 , I am doing that by working on a 3X3 matrix and 4 X 4 matrix. <BR> u = <BR> 1 -1 0<BR> 0 1 -1<BR> <BR>octave-3.2.4.exe:54> transpose(u)*u <BR>ans = 1 -1 0<BR> -1 2 -1<BR> 0 -1 1<BR> – newbietolinalg Mar 14 '12 at 19:03

## 3 Answers

Let $S$ be the $N\times (N+1)$ matrix with $S_{i+1,i}=1$ ($i=1,\ldots,N$) and $0$ everywhere else. Write $I_N$ for the $N\times N$ identity matrix, and $J_N$ for the $N\times(N+1)$ matrix with $J_N(i,i)=1$ and zero everywhere else.

It is easy to see that $S^TS=I_N$, and that $C_N=J_N-S^T$. Using that $J_N^TJ_N=I_N$, that $J_N$ is a right identity, and that $J_N^T$ is a left identity,

$$C_NC_N^T=(J_N^T-S^T)(J_N-S^T)=J_N^TJ_N+S^TS-J_N^TS^T-SJ_N=2I_N-S^T-S=B_N.$$

-

Write $C_N^{ij}=\delta_{ij}-\delta_{i+1,j}$ where $\delta_{ij}:=\begin{cases}1&\mbox{ if }i=j\\\ 0&\mbox{ otherwise}\end{cases}.$

We have for $1\leq j\leq N$ $$(C_NC_N^T)_{jj}=\sum_{k=1}^{N+1}C_N^{jk}C_N^{jk}=\sum_{k=1}^{N+1}(\delta_{jk}-\delta_{j+1,k})^2=\sum_{k=1}^{N+1}\delta_{jk}+\sum_{k=1}^{N+1}\delta_{j+1,k}+ \sum_{k=1}^{N+1}\delta_{jk}\delta_{j+1,k}=2.$$ Now, since we know that $C_NC_N^T$ is symmetric, compute $(C_NC_N^T)^{j,j+1}$ for $1\leq j\leq N-1$ by the same way.

-

Note $C_N = \begin{bmatrix}c_1 \\ c_2 \\ c_3 \\ \vdots \\ c_N \end{bmatrix}$ where $c_k$ is a row vector of length $N+1$ with the $k^{th}$ entry being $1$ and $(k+1)^{th}$ entry being $-1$. Let $D_N = C_N C_N^T$, we have $$D_N(i,j) = \displaystyle \sum_{k=1}^{N+1} C_N(i,k) C_N^T(k,j) = \sum_{k=1}^{N+1} c_i(k) c_j(k)$$ Note that $c_i(k) = \begin{cases} 1 & \text{if }k=i\\ -1 & \text{if }k=i+1\\ 0 & \text{otherwise} \end{cases}$. Hence, $D_N(i,j) = c_i(i)c_j(i) + c_i(i+1)c_j(i+1) = c_j(i) - c_j(i+1)$. Now again,

1. If $i<j-1$ or $i>j+1$, then $c_j(i) = 0$ and $c_j(i+1) = 0$. Hence, $D_N(i,j) = 0$.
2. If $i=j-1$, then $c_j(i) = 0$ and $c_j(i+1) = 1$. Hence, $D_N(i,j) = -1$.
3. If $i=j$, then $c_j(i) = 1$ and $c_j(i+1) = -1$. Hence, $D_N(i,j) = 2$.
4. If $i=j+1$, then $c_j(i) = -1$ and $c_j(i+1) = 0$. Hence, $D_N(i,j) = -1$.

Hence, $$D_N(i,j) = \begin{cases} 2 & \text{if } i=j\\ -1 & \text{if }|i-j| = 1\\ 0 & \text{if }|i-j| > 1 \end{cases}$$ which is the same as $B_N(i,j)$.

-