Solving linear system with triangular Toeplitz matrix

I hand calculated the first 6 with forward substitution and found that if you let $\mathcal{M}_{i,j}$ be the set of ordered pairs of integers $(m_1,m_2,...,m_{j-1})$ such that $\sum\limits_{k=1}^{j-1}m_k=i+j-2$ and each $m_k\ge 2$, then for $i>1$ you will have $a_i=\sum\limits_{j=2}^i\frac{(-1)^{j+1}}{b_1^j}\big[\sum\limits_{(m_1,...,m_{j-1})\in \mathcal{M}_{i,j}}b_{m_1}b_{m_2}...b_{m_{j-1}}\big]$. Of course for $i=1$ you have $a_1=\frac{1}{b_1}$.

Here is a proof by strong induction I just wrote.

The base cases for $i=1,2$ are easy to show with forward substitution. Now let $i\ge2$ and assume the hypothesis holds for all $k\le i$, then $$a_{i+1}=-\frac{1}{b_1}\sum\limits_{k=1}^{i}b_{i+2-k}a_k$$$$=-\frac{1}{b_1}\Big(\frac{b_{i+1}}{b_1}+\sum\limits_{k=2}^{i}b_{i+2-k}\sum\limits_{j=2}^k\frac{(-1)^{j+1}}{b_1^j}\big[\sum\limits_{(m_1,...m_{j-1})\in\mathcal{M}_{k,j}}b_{m_1}b_{m_2}...b_{m_{j-1}}\big]\Big)$$$$=-\frac{b_{i+1}}{b_1^2}+\sum\limits_{k=2}^i\sum\limits_{j=2}^k\frac{(-1)^{j+2}}{b_1^{j+1}}\big[\sum\limits_{(m_1,...m_{j-1})\in\mathcal{M}_{k,j}}b_{m_1}b_{m_2}...b_{m_{j-1}}b_{i+2-k}\big]$$

Notice for each $2\le k\le i$ and $2\le j\le k$, it is clear that $(m_1,...,m_{j-1})\in\mathcal{M}_{k,j}$ implies $(m_1,...,m_{j-1},i+2-k)\in\mathcal{M}_{i+1,j+1}$. Furthermore, for each $2\le j\le i$ and $(m_1,...,m_j)\in\mathcal{M}_{i+1,j+1}$, since each entry of the ordered pair is greater than or equal to $2$ and the entries sum to $i+j$, we must have $m_j\le i+j-2(j-1)=i-j+2$, implying $m_j=i+2-k$ for some unique $k$ with $j\le k \le i$, and of course $(m_1,...,m_{j-1})\in\mathcal{M}_{k,j}$. It follows that the previous double sum is equivalent to $$\sum\limits_{j=2}^i\frac{(-1)^{j+2}}{b_1^{j+1}}\big[\sum\limits_{(m_1,...m_{j})\in\mathcal{M}_{i+1,j+1}}b_{m_1}b_{m_2}...b_{m_j}\big]=\sum\limits_{j=3}^{i+1}\frac{(-1)^{j+1}}{b_1^{j}}\big[\sum\limits_{(m_1,...m_{j-1})\in\mathcal{M}_{i+1,j}}b_{m_1}b_{m_2}...b_{m_{j-1}}\big]$$ Substituting back into the formula for $a_{i+1}$ and noting that $\mathcal{M}_{i+1,2}=\{(i+1)\}$, we have $$a_{i+1}=-\frac{b_{i+1}}{b_1^2}+\sum\limits_{j=3}^{i+1}\frac{(-1)^{j+1}}{b_1^{j}}\big[\sum\limits_{(m_1,...m_{j-1})\in\mathcal{M}_{i+1,j}}b_{m_1}b_{m_2}...b_{m_{j-1}}\big]$$$$=\sum\limits_{j=2}^{i+1}\frac{(-1)^{j+1}}{b_1^{j}}\big[\sum\limits_{(m_1,...m_{j-1})\in\mathcal{M}_{i+1,j}}b_{m_1}b_{m_2}...b_{m_{j-1}}\big]$$ This proves the result.

Rephrasing slightly,

$$ \begin{bmatrix} b_0 & 0 & \cdots & 0 & 0 \\ b_1 & b_0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ b_{n-2} & b_{n-3} & \cdots & b_0 & 0 \\ b_{n-1} & b_{n-2} & \cdots & b_1 & b_0 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n-2} \\ a_{n-1} \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \\ 0 \end{bmatrix} $$

where $b_0 \neq 0$. Note that the LHS is the (discrete) convolution of sequences $a$ and $b$. One would like to find the sequence $a$ of length $n$ such that $a \star b = \delta$, where $\delta$ is a unit pulse. In signal processing, one would call this deconvolution. In communications engineering, one would call this channel equalization. Taking the $\cal{Z}$-transforms of both sides of $a \star b = \delta$,

$$ \left( \sum_{k=0}^{n-1} a_k z^{-k} \right) \left( \sum_{\ell=0}^{n-1} b_{\ell} z^{-\ell} \right) = 1 $$

and, thus, $a_k$ is the coefficient of $z^{-k}$ in $\left( \sum\limits_{\ell=0}^{n-1} b_{\ell} z^{-\ell}\right)^{-1}$.

Related

• What are practical examples of Toeplitz matrices?

convolution deconvolution toeplitz-matrices