Bandwidth of a matrix: Difference between revisions

Revision as of 17:16, 1 May 2014

Definition

Suppose $n$ is a positive integer and $A = (a_{i j})_{1 \leq i \leq n, 1 \leq j \leq n}$ is a $n \times n$ square matrix.

The left half-bandwidth of $A$ is defined as the smallest positive integer $k_{1}$ such that $a_{i j} = 0$ whenever $j < i - k_{1}$ . In other words, entries that are more than $k_{1}$ positions below the main diagonal are zero.

The right half-bandwidth of $A$ is defined as the smallest positive integer $k_{2}$ such that $a_{i j} = 0$ whenever $j < i + k_{2}$ . In other words, entries that are more than $k_{2}$ positions above the main diagonal are zero.

The banwidth is defined as $k_{1} + k_{2} + 1$ , where $k_{1}, k_{2}$ are the left and right half-bandwidths respectively.

Ambiguity with terminology

When we say that a matrix has a given bandwidth (respectively, a given left half-bandwidth or a given right half-bandwidth) what we mean is that the bandwidth (respectively, the left or right half-bandwidth) is at most that quantity, not that it is necessarily exactly equal to that quantity.

Particular cases

Matrix type (all matrices are $n \times n$ )	Left half-bandwidth (upper bound)	Right half-bandwidth (upper bound)	Bandwidth (upper bound)
diagonal matrix	0	0	1
tridiagonal matrix	1	1	3
pentadiagonal matrix	2	2	5
upper triangular matrix	0	$n - 1$	$n$
lower triangular matrix	$n - 1$	0	$n$

@@ Line 3: / Line 3: @@
 Suppose <math>n</math> is a positive integer and <math>A = (a_{ij})_{1 \le i \le n, 1 \le j \le n}</math> is a <math>n \times n</math> [[square matrix]].
-The '''left half-bandwidth''' of <math>A<math> is defined as the smallest positive integer <math>k_1</math> such that <math>a_{ij} = 0</math> whenever <math>j < i - k_1</math>. In other words, entries that are more than <math>k_1</math> positions below the [[main diagonal]] are zero.
+The '''left half-bandwidth''' of <math>A</math> is defined as the smallest positive integer <math>k_1</math> such that <math>a_{ij} = 0</math> whenever <math>j < i - k_1</math>. In other words, entries that are more than <math>k_1</math> positions below the [[main diagonal]] are zero.
 The '''right half-bandwidth''' of <math>A</math> is defined as the smallest positive integer <math>k_2</math> such that <math>a_{ij} = 0</math> whenever <math>j < i + k_2</math>. In other words, entries that are more than <math>k_2</math> positions above the [[main diagonal]] are zero.