Bandwidth of a matrix: Difference between revisions

Latest revision as of 17:40, 1 May 2014

Definition

Suppose $n$ is a positive integer and $A=(a_{ij})_{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_{ij}=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_{ij}=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.

The notion of band matrix or banded matrix

The term band matrix or banded matrix is used for a matrix whose bandwidth is reasonably small.

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.
@@ Line 12: / Line 12: @@
 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.
+===The notion of band matrix or banded matrix===
+The term '''band matrix''' or '''banded matrix''' is used for a matrix whose bandwidth is reasonably small.
+==Particular cases==
+{| class="sortable" border="1"
+! Matrix type (all matrices are <math>n \times n</math>) !! 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 || <math>n - 1</math> || <math>n</math>
+|-
+| [[lower triangular matrix]] || <math>n - 1</math> || 0 || <math>n</math>
+|}