6

I was solving a problem which involved finding the bandwidth of a matrix. I interpreted the bandwidth as a non-negative number which is closest to the diagonal. And this interpretation of mine does work on some examples. However, the condition is:

Bandwidth of a matrix A is defined as the smallest non-negative integer K such that A(i, j) = 0 for |i - j| > K.

Now, I am confused as the condition says that a[i,j] should be 0 and |i-j| of the same should be > K. I am not able to figure out why a[i,j] should be 0. Please help me clearing what K is and what does this condition evaluate to.

Aniket
  • 63

1 Answers1

3

Take the matrix

$$A = \begin{bmatrix} 3 & 1 & 4 & 0 & 0 & 0 \\ 1 & 5 & 9 & 2 & 0 & 0 \\ 6 & 5 & 3 & 5 & 8 & 0 \\ 0 & 9 & 7 & 9 & 3 & 2 \\ 0 & 0 & 3 & 8 & 4 & 6 \\ 0 & 0 & 0 & 2 & 6 & 4 \end{bmatrix}$$

as an example. To figure out what the bandwidth is from your definition, we need to figure out the smallest value of $K$ that satisfies the condition.

In this case, $K=2$ works, because whenever $|i-j|>2$, we have $A_{i,j}=0$. The pairs $(i,j)$ with $|i-j|>2$ are $(1,4), (1,5), (1,6), (2,5), (2,6), (3,6), (4,1), (5,1), (5,2), (6,1), (6,2), (6,3)$ and you can see that $A_{1,4} = A_{1,5} = \dots = A_{6,3} = 0$.

But $K=1$ does not work: we can choose $i$ and $j$ such that $|i-j|>1$ but $A_{i,j} \ne 0$. For example, $(i,j) = (1,3)$ works: $|1-3|>1$ and $A_{1,3} \ne 0$.

So $K=2$ is the smallest $K$ that works, and this matrix has bandwidth 2.

(Equivalently, having a bandwidth of $K$ or less tells you that all the nonzero entries of the matrix are within $K$ steps of the diagonal, which you can see in this example.)

Misha Lavrov
  • 142,276
  • Thanks for your reply, What if my matrix is: "1 0 0" "0 1 1" "1 1 0" . The bandwidth here is supposed to be 2, but I can't find an a[i,j]=0. – Aniket Mar 15 '17 at 09:36
  • So in your example, it's trivially true that "For all $i,j$ with $|i-j|>2$, $A_{i,j}=0$" because the matrix has no entries $A_{i,j}$ with $|i-j|>2$: the furthest from the diagonal you can get is $A_{1,3}$ which has $|i-j|=2$. In other words and slightly more generally, an $n \times n$ matrix will have bandwidth at most $n-1$. – Misha Lavrov Mar 15 '17 at 15:15