How can one show that the product of two banded matrices is a banded matrix with upper and lower bandwidths equal to the sum of the upper and lower bandwidths (respectively) of the multiplicands ? Thank you
$\endgroup$ 21 Answer
$\begingroup$For a band matrix $A$ with bandwidth $p + q + 1$, where $p \ge 0$ is the lower bandwidth and $q \ge 0$ is the upper bandwidth, we have the implication: $$ (p + j < i) \vee (q + i < j) \Rightarrow a_{ij} = 0 $$ where the first condition is for the lower zero area, and the second conditon for the upper zero area.
Similar for a band matrix $B$ with bandwidth $r + s + 1$ we can write
$$
(r + j < i) \vee (s + i < j) \Rightarrow b_{ij} = 0
$$
For the matrix product $C = A B$ we have the elements
$$
c_{ik} = \sum_{j=1}^n a_{ij} b_{jk}
$$
For these elements the implications
$$
(p + j < i) \vee (q + i < j) \Rightarrow (a_{ij} = 0) \\
(r + k < j) \vee (s + j < k) \Rightarrow (b_{jk} = 0)
$$
hold.
For non-zero elements $c_{ik}$ we need at least one $j$ with:
$$
a_{ij} \ne 0 \Rightarrow
\neg ((p + j < i) \vee (q + i < j))
= (p + j \ge i) \wedge (q + i \ge j)
$$
and
$$
b_{jk} \ne 0 \Rightarrow
\neg ((r + k < j) \vee (s + j < k))
= (r + k \ge j) \wedge (s + j \ge k)
$$
thus
$$
(p + j \ge i) \wedge (q + i \ge j) \wedge
(r + k \ge j) \wedge (s + j \ge k)
$$
this is equivalent to
$$
(p + r + k \ge p + j) \wedge (p + j \ge i) \wedge
(q + s + i \ge s + j) \wedge (s + j \ge k)
$$
where we added
$p$ to both sides of the third inequality and
$s$ to both sides of the second inequality.
Using transitivity of the $\ge$ relation
$$
(\alpha \ge \beta) \wedge (\beta \ge \gamma) \Rightarrow \alpha \ge \gamma
$$
this implies
$$
(\exists j : (a_{ij} \ne 0) \wedge (b_{jk} \ne 0)) \Rightarrow
(p + r + k \ge i) \wedge (q + s + i \ge k)
$$
as necessary condition for the non-zero elements and thus
$$
(p + r + k < i) \vee (q + s + i < k) \Rightarrow
(\forall j : (a_{ij} = 0) \vee (b_{jk} = 0)) \Rightarrow
(c_{ik} = 0)
$$
as sufficient condition for the zero elements of $C$.
This characterizes a band matrix of lower bandwidth $p + r$ and higher bandwidth $q + s$.
