띠행렬

띠행렬

행렬론에서 띠행렬(-行列, 영어: band matrix)은 모든 0이 아닌 성분이 주대각선 주변에 집중된 희소 행렬이다.

정의

환 $R$의 원소를 성분으로 하는 $m\times n$ 행렬 $M$의 하대역폭(下帶域幅, 영어: lower bandwidth)은 다음 조건을 만족시키는 음이 아닌 정수 $p$이다.^{:15, §1.2.1}

• 만약 $i>j+p$라면, $M_{ij}=0$이다.

환 $R$의 원소를 성분으로 하는 $m\times n$ 행렬 $M$의 상대역폭(上帶域幅, 영어: upper bandwidth)은 다음 조건을 만족시키는 음이 아닌 정수 $p$이다.^{:15, §1.2.1}

• 만약 $j>i+p$라면, $M_{ij}=0$이다.

환 $R$의 원소를 성분으로 하는 $m\times n$ 행렬 $M$의 대역폭(帶域幅, 영어: bandwidth)은 $M$의 하대역폭이자 상대역폭인 가장 큰 음이 아닌 정수이다. 즉, 다음 조건을 만족시키는 가장 큰 음이 아닌 정수 $k$이다.

• 만약 $|i-j|>k$라면, $M_{ij}=0$이다.

예를 들어, 하대역폭 2 및 상대역폭 1를 갖는 9×4 띠행렬은 다음과 같은 꼴이다 ($M_{ij}\in R$).

${\begin{pmatrix}M_{11}&M_{12}&0&0\\M_{21}&M_{22}&M_{23}&0\\M_{31}&M_{32}&M_{33}&M_{34}\\0&M_{42}&M_{43}&M_{44}\\0&0&M_{53}&M_{54}\\0&0&0&M_{64}\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{pmatrix}}$

예

특수한 하대역폭·상대역폭을 갖는 띠행렬에는 다음과 같은 이름이 붙는다.^{:15, §1.2.1, Table 1.2.1}

하대역폭	상대역폭	이름
0	0	대각 행렬
0	1	상쌍대각 행렬(영어: upper bidiagonal matrix)
1	0	하쌍대각 행렬(영어: lower bidiagonal matrix)
1	1	3중 대각 행렬(영어: tridiagonal matrix)
2	2	5중 대각 행렬(영어: pentadiagonal matrix)
3	3	7중 대각 행렬(영어: heptadiagonal matrix)
0	$n-1$	상삼각 행렬
$m-1$	0	하삼각 행렬
1	$n-1$	상헤센베르크 행렬
$m-1$	1	하헤센베르크 행렬

응용

띠저장

컴퓨팅에서, 좁은 대역폭의 띠행렬을 더 작은 크기의 행렬로서 저장하여 행렬 알고리즘의 저장 효율을 높일 수 있다. 이를 띠저장(-貯藏, 영어: band storage)이라고 한다.

구체적으로, 하대역폭 $p$ 및 상대역폭 $q$를 갖는 $n\times n$ 띠행렬 $M$은 다음과 같은 $(p+q+1)\times n$ 행렬 $\operatorname {band} (M)$에 대응하며, 만약 $p,q\ll n$일 경우 이는 원래의 행렬보다 훨씬 작다.^{:17, §1.2.5, (1.2.1)}

$\operatorname {band} (M)_{ij}={\begin{cases}M_{i+j-q-1,j}&i+j-q-1\in \{1,\dots ,m\}\\0&i+j-q-1\not \in \{1,\dots ,m\}\end{cases}}$

예를 들어, 하대역폭 1 및 상대역폭 1를 갖는 6×6 띠행렬

$M={\begin{pmatrix}M_{11}&M_{12}&0&0&0&0\\M_{21}&M_{22}&M_{23}&0&0&0\\0&M_{32}&M_{33}&M_{34}&0&0\\0&0&M_{43}&M_{44}&M_{45}&0\\0&0&0&M_{54}&M_{55}&M_{56}\\0&0&0&0&M_{65}&M_{66}\\\end{pmatrix}}$

은 다음과 같은 3×6행렬로 저장할 수 있다.

$\operatorname {band} (M)={\begin{pmatrix}0&M_{12}&M_{23}&M_{34}&M_{45}&M_{56}\\M_{11}&M_{22}&M_{33}&M_{44}&M_{55}&M_{66}\\M_{21}&M_{32}&M_{43}&M_{54}&M_{65}&0\end{pmatrix}}$

외부 링크

• Weisstein, Eric Wolfgang. “Bandwidth”. 《Wolfram MathWorld》 (영어). Wolfram Research.