Show that the lower triangular matrix $L=(l_{ij})i,j=1,…,n∈Rn×n$ resulting from Cholesky decomposition has the same band width m as the band matrix A Let $ A=\left(a_{i j}\right)_{i, j=1, \ldots, n} \in \mathbb{R}^{n \times n} $ be a symmetric and positive definite band matrix with band width $ m \in \mathbb{N} $, i.e. $ a_{i j}=0 $ for $ i, j \in \mathbb{N} $ with $ |i-j|>m $.
Show that the lower triangular matrix $ L=\left(l_{i j}\right)_{i, j=1, \ldots, n} \in \mathbb{R}^{n \times n} $ resulting from the Cholesky decomposition has the same band width $ m $.  This means $ l_{i j}=0 $ for $ i, j \in \mathbb{N} $ with $ i-j>m $.
This statement is a theorem from my script on Numerical Linear Algebra 1. I tried a few examples and indeed the band structure of the band matrix A is preserved. But this is a big advantage, because if you write the algorithm for it, you can avoid the places where the zeros are at A with the bandwidth m and you have to calculate less.
To perhaps prove the theorem, one could use induction, but am not sure where that would lead.
Here is also the corresponding algorithm:
Cholesky decomposition for symmetric positive definite band matrices
I finally found the task in a book with a description of the proof, but unfortunately it makes little sense to me, maybe someone can explain it or has another idea because of that.
Proof from the mentioned book (in German)
Proof. It suffices to show that the first reduction step described by
$l_{11} =\sqrt{a_{11}} ; \quad l_{i 1}=\frac{a_{i 1}}{\sqrt{a_{11}}}=\frac{a_{i 1}}{l_{11}}, \quad i=2,3, \ldots, n ; \hspace{1cm} (*)$
$a_{i k}^{(1)} =a_{i k}-\frac{a_{i 1} a_{1 k}}{a_{11}}=a_{i k}-l_{i 1} l_{k 1}, \quad i, k=2,3, \ldots, n \hspace{1cm} (**)$
in the first column of $ \boldsymbol{L} $ below the diagonal (1) produces nonzero elements only in the $ m $ side diagonals, and (2) that the reduced matrix $ \boldsymbol{A}^{(1)}=\left(a_{i k}^{(1)}\right) $ has the same width $ m $.
(1) Assertion: is true because of $(*)$, since it is $ l_{i 1}=0 $ for all $ i $ with $ i-1>m $, since then by premise $ a_{i 1}=0 $.
(2) Assertion: for symmetry reasons one needs only elements ( a_{i k}^{(1)} ) below the diagonal. For any place $ (i, k) $ with $ i \geq k \geq 2 $ and $ i-k>m $, on the one hand, according to the premise $ a_{i k}=0 $ and, on the other hand, due to the statement just made $ l_{i 1}=0 $, because it is $ i-1>i-k>m $.
Thus, because of $(**)$ in fact $ a_{i k}^{(1)}=0 $ holds for all $ i, k \geq 2 $ with $|i-k|>m $.
 A: Let $A \in \mathbb{R}^{n \times n}$ be symmetric positive definite with upper and lower bandwidth $m$. Partition the matrix $A$ and the Cholesky factor as $2$-by-$2$ block matrices where the upper left corners are $1$-by-$1$ matrices, and the lower right corners are square matrices of dimension $(n-1)$, i.e.,
$$A = \begin{bmatrix} \alpha & u^T \\ u & A_{22} \end{bmatrix} = \begin{bmatrix} l & 0 \\ v & L_{22} \end{bmatrix} \begin{bmatrix} l & v^T \\ 0 & L_{22}^T \end{bmatrix} = \begin{bmatrix} l^2 & l v^T \\ vl & L_{22}L_{22}^T + vv^T\end{bmatrix}$$
Only the first $m$ components of the column vector $u \in \mathbb{R}^{n-1}$ can be non-zero because $A$ has lower bandwidth $m$. It follows that $$v = u/l$$ has the same property. The Schur complement matrix $$S_{22} = L_{22} L_{22}^T = A_{22} - vv^T$$ is banded with upper and lower bandwidth $m$, because $A_{22}$ has this property and the entries of $vv^T$ are zero outside of the upper-left $m$-by-$m$ corner.

This shows how to reduce the dimension of the active matrix by one while preserving the upper bound on the half-bandwidth. A rigorous proof would apply the well-ordering principle rather than the principle of mathematical induction.
