띠행렬

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

띠행렬

정의

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

예

특수한 하대역폭·상대역폭을 갖는 띠행렬에는 다음과 같은 이름이 붙는다.^{[1]: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	${\displaystyle n-1}$	상삼각 행렬
${\displaystyle m-1}$	0	하삼각 행렬
1	${\displaystyle n-1}$	상헤센베르크 행렬
${\displaystyle m-1}$	1	하헤센베르크 행렬

응용

띠저장

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

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

${\displaystyle \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 띠행렬

${\displaystyle 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행렬로 저장할 수 있다.

${\displaystyle \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}}}$

같이 보기

• 대각 행렬