1
$\begingroup$

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.

  • 0
    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.
    u =
    1 -1 0
    0 1 -1

    octave-3.2.4.exe:54> transpose(u)*u
    ans = 1 -1 0
    -1 2 -1
    0 -1 1
    2012-03-14

3 Answers 3

1

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. $

0

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.

0

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 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)$.