|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
隣 接 行 列, adjacency matrix그래프에서 각 정점(vertex)의 연결 관계, 즉 간선(edge)의 존재 여부를 행렬로 표현한 것이다. 그래프에서 정점이 [math(n)]개일 때, 각 정점을 행과 열로 하는 [math(n)]차 정사각행렬이다.
2. 표현 방법
정점이 n개인 그래프의 각 정점에 대해 순서대로 [math(1, 2, ..., n)]으로 번호를 매길 때, 이 그래프에 대한 인접행렬을 [math(A)]라고 하면 다음과 같은 규칙을 따른다. (단, [math(a, b=1, 2, ..., n)])- [math(A_{ab})] 성분의 값은 정점 [math(a)]에서 [math(b)]로 이동하는 간선이 있을 때 1, 없을 때 0이다.
- 무방향 그래프일 때는 [math(a)]와 [math(b)]를 연결하는 간선이 있으면 1, 그렇지 않으면 0이다.
- [math(A_{aa})] 성분, 즉 주대각선상의 성분의 값은 항상 0이다.
- 단 자기 자신으로 연결되는 간선이 있으면 1이다.
예를 들어 위 그림에서 정점 A, B, C, D, E를 각각 숫자 1, 2, 3, 4, 5로 번호를 매기면 (가)는 무방향 그래프이므로 인접행렬은 다음과 같이 대칭행렬이다.
[math(A_{가}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})]
(나)는 방향 그래프이고, 그 인접행렬은 다음과 같다.
[math(A_{나}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})]
(다)는 무방향 간선이 존재하는 방향 그래프이고, 그 인접행렬은 다음과 같다.
[math(A_{다}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})]
(가), (나), (다) 모두 자기 자신으로 이동하는 간선은 존재하지 않으므로 주대각선상의 성분의 값은 항상 0이 된다.3. 성질
-
무방향 그래프의 인접행렬은 항상 대칭행렬이다.
무방향 그래프라는 것은 정점 [math(a)]에서 [math(b)]로 이동하는 간선이 있을 때 정점 [math(b)]에서 [math(a)]로 이동하는 간선 역시 항상 존재한다는 것을 의미하고, 그 역도 성립한다. 따라서 인접행렬 [math(A)]에 대해서 [math(A_{ab}=A_{ba})]가 항상 성립한다. - 인접행렬의 모든 성분의 합은 그래프의 화살표의 개수와 같다. 이때, 무방향 간선은 양쪽으로 이어지므로 화살표 2개로 간주한다.
- 무방향 그래프에서 인접행렬의 모든 성분의 합은 간선의 개수의 2배이다.
4. 경로의 개수
인접행렬을 이용하여 정점의 개수가 [math(v)]개인 그래프의 어떤 정점 [math(a)]에서 다른 정점 [math(b)]로 이동하는 경로의 개수를 구할 수 있다. 인접행렬 [math(A)]에 대하여 [math(A^n)]은 어떤 정점에서 다른 정점으로 [math(n)] step을 거쳐서 이동하는 경로의 수를 나타낸다. 즉, [math(A^n_{ab})]는 그래프의 정점 [math(a)]에서 정점 [math(b)]로 [math(n)] step을 거쳐 이동하는 가능한 경로의 수이다. 증명은 수학적 귀납법을 사용하면 다음과 같다.- 먼저 [math(n=1)]일 때, 인접행렬 [math(A)]의 성분 [math(A_{ab})] 그 자체는 그래프의 정점 [math(a)]에서 [math(b)]로 직접 이동하는 경로가 있으면 1, 없으면 0이다. 즉 1 step을 거쳐 [math(a)]에서 [math(b)]로 이동하는 경로가 있는지를 나타내므로, 이러한 경로의 개수와 같다.
- [math(n=k)]일 때 [math(A^k_{ab})] 성분을 그래프에서 정점 [math(a)]에서 [math(b)]로 [math(k)] step을 거쳐 이동하는 경로의 개수라고 하자. 이때 [math(A^{k+1}_{ab})]은 [math(A^{k+1}_{ab}=\sum_{i=1}^v A^k_{ai}A_{ib})]와 같이 구할 수 있다. 이때 [math(A^k_{ai})]는 정점 [math(a)]에서 [math(i)]로 [math(k)] step을 거쳐 이동하는 경로의 개수를, 그리고 [math(A_{ib})]는 정점 [math(i)]에서 [math(b)]로 직접 이동할 수 있는지를 나타낸다. 이 식의 각 항 [math(A^k_{ai}A_{ib})] (단, [math(i=1,2,...,v)])은 이 둘을 곱한 것과 같으므로, 정점 [math(i)]에서 [math(b)]로 직접 이동할 수 있으면 정점 [math(a)]에서 [math(i)]로 [math(k)] step을 거쳐 이동하는 경로의 개수가 되고, 이동할 수 없으면 그 경로의 개수와 상관없이 0이 된다. 따라서 정점 [math(a)]에서 [math(k)] step 만에 정점 [math(i)]를 거치고, 이후 1 step 만에 정점 [math(b)]에 도달하는 경우의 수와 같다. 따라서 그 합인 [math(A^{k+1}_{ab}=\sum_{i=1}^v A^k_{ai}A_{ib})]는 각 정점 [math(i=1,2,...,v)]에 대해 그 경우의 수를 모두 합한 것이므로, 정점 [math(a)]에서 정점 [math(b)]까지 [math(k+1)] step 만에 이동하는 경우의 수가 된다. 즉 [math(n=k)]일 때 [math(A^k_{ab})] 성분이 정점 [math(a)]에서 [math(b)]로 [math(k)] step 만에 이동하는 경우의 수이면, [math(n=k+1)]일 때 [math(A^{k+1}_{ab})] 성분은 [math(k+1)] step 만에 이동하는 경우의 수이다.
- 따라서 수학적 귀납법에 의해 이것이 1 이상의 모든 자연수에 대해 성립한다.
더 간단히 말해보자.
[math((A(n))_{ab})]를 [math(a)]에서 [math(b)]까지 [math(n)]번 이동해 도달하는 경로의 수라고 하자.
[math((A(n+m))_{ab})]는 모든 [math(k)]에 대하여 [math(a)]에서 시작, [math(n)]번 이동해 [math(k)]에 경유하고 다시 [math(m)]번 이동해 [math(b)]에 도달하는 경로수의 합이다. [math(k)]를 경유하는 경로수는 [math(a)]에서 [math(k)]로 [math(n)]번 이동한 경로수와 [math(k)]에서 [math(b)]로 [math(m)]번 이동하는 경로수의 곱이다. 따라서 [math(A(n+m)_{ab} = \displaystyle \sum_{k} (A(n))_{ak}(A(m))_{kb})]이다. 행렬곱에 의해 즉, [math(A(n+m)=A(n)A(m))]이다.
내부 자연수를 쪼개 각 행렬의 곱으로 표현할 수 있으므로 [math(1)]로 모두 쪼개어 [math(A(n)=A(1)^n)]이다. [math(A(1)=A)]로 인접행렬이므로, [math(A(n)=A^n)]이다. 즉, 증명되었다.
[math((A(n))_{ab})]를 [math(a)]에서 [math(b)]까지 [math(n)]번 이동해 도달하는 경로의 수라고 하자.
[math((A(n+m))_{ab})]는 모든 [math(k)]에 대하여 [math(a)]에서 시작, [math(n)]번 이동해 [math(k)]에 경유하고 다시 [math(m)]번 이동해 [math(b)]에 도달하는 경로수의 합이다. [math(k)]를 경유하는 경로수는 [math(a)]에서 [math(k)]로 [math(n)]번 이동한 경로수와 [math(k)]에서 [math(b)]로 [math(m)]번 이동하는 경로수의 곱이다. 따라서 [math(A(n+m)_{ab} = \displaystyle \sum_{k} (A(n))_{ak}(A(m))_{kb})]이다. 행렬곱에 의해 즉, [math(A(n+m)=A(n)A(m))]이다.
내부 자연수를 쪼개 각 행렬의 곱으로 표현할 수 있으므로 [math(1)]로 모두 쪼개어 [math(A(n)=A(1)^n)]이다. [math(A(1)=A)]로 인접행렬이므로, [math(A(n)=A^n)]이다. 즉, 증명되었다.
무방향 그래프인 경우 인접행렬이 대칭행렬이므로 몇 제곱을 하든지 여전히 대칭행렬이다. 따라서 무방향 그래프에서 [math(A^n_{ab})], 즉 정점 [math(a)]에서 [math(b)]로 [math(n)] step 만에 이동하는 경로의 수는 [math(A^n_{ba})], 즉 정점 [math(b)]에서 [math(a)]로 [math(n)] step 만에 이동하는 경로의 수와 같음을 알 수 있다.
인접행렬 [math(A)]에 대해서 [math(A^2)]의 주대각선의 성분은 각 정점에서 출발하여 그 정점으로 2 step 만에 돌아오는 경우의 수를 의미하므로, 무방향 그래프에서는 해당 정점과 직접 연결된 다른 정점의 개수, 즉 간선의 개수를 나타내고, 방향 그래프에서는 해당 정점과 쌍방 직접 연결된 다른 정점의 개수를 나타낸다.
sparse graph가 아닌 경우, 즉 각 정점들이 어느 정도 이상 연결되어 있는 경우 [math(A^n)]에서 [math(n)]이 커질수록 각 성분의 값, 즉 특정 정점에서 다른 정점으로 [math(n)] step 만에 이동하는 경로의 수도 늘어나는 추세를 보인다. 각 정점들 간에 상당수 연결되어 있는 경우에는 기하급수적으로 늘어나는 추세를 보인다. sparse한 무방향 그래프이거나, 방향 그래프이더라도 일부 정점들이 cycle 형태로 연결된 그래프의 경우에는 같은 이동 경로를 무한히 반복할 수 있기 때문에 [math(n)]의 값이 커져도 각 성분의 값이 0으로 수렴하지 않지만, cycle이 없는 방향 그래프의 경우 그래프 내에서 정점의 개수 이상의 횟수로 이동하는 것이 불가능하므로 [math(n)]이 커지면 각 성분의 값이 0으로 수렴하며, 정점의 수 이상으로 커지면 반드시 영행렬이 된다. 정확히는 순서대로 이동할 수 있는 정점의 chain의 최대 길이가 [math(l)]인 경우, [math(A^{l-1})]까지는 영행렬이 아니며 [math(A^l)]부터 영행렬이다.
4.1. 예시
예를 들어 위 그림의 그래프 (가)의 인접행렬 [math(A_{가})]의 제곱은 다음과 같다.
[math(A_{가}^2=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix}^2=\begin{pmatrix}2 & 1 & 1 & 1 & 1 \\ 1 & 3 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 3 & 0 \\ 1 & 1 & 0 & 0 & 1\end{pmatrix})]
여기서 정점 C→정점 D로 2 step 만에 이동하는 경로의 수는 [math({A_{가}^2}_{34})] 성분과 같으므로 1개이다. 실제로 구해 보면 C→B→D의 1개밖에 존재하지 않는다. 주대각선을 보면 정점 A에서 자기 자신으로 2 step만에 이동하는 경로의 수는 [math({A_{가}^2}_{11}=2)]로, A와 이웃한 정점(B, D)의 개수와 같다. 실제로 경로를 찾아보면 A→B→A, A→D→A의 2가지뿐이다.한편 이때 [math(A_{가})]의 세제곱은 다음과 같다.
[math(A_{가}^3=\begin{pmatrix}2 & 4 & 1 & 4 & 1 \\ 4 & 2 & 3 & 5 & 1 \\ 1 & 3 & 0 & 1 & 1 \\ 4 & 5 & 1 & 2 & 3 \\ 1 & 1 & 1 & 3 & 0\end{pmatrix})]
여기서 정점 B에서 D로 3 step 만에 이동하는 경로의 수는 [math({A_{가}^3}_{24})] 성분과 같으므로 5개이다. 실제로 찾아보면 B→A→B→D, B→C→B→D, B→D→A→D, B→D→B→D, B→D→E→D로 5가지이다.방향 그래프인 그래프 (나)의 인접행렬 [math(A_{나})]의 제곱은 다음과 같다.
[math(A_{나}^2=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix}^2=\begin{pmatrix}0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0\end{pmatrix})]
여기서 정점 A→정점 D로 2 step 만에 이동하는 경로의 수는 [math({A_{나}^2}_{14})] 성분과 같으므로 1개이다. 실제로 구해 보면 A→B→D의 1개밖에 존재하지 않는다. 주대각선의 성분은 모두 0인데, 이는 모든 각 정점에 대해서 쌍방향으로 연결된 간선이 단 하나도 없다는 것을 의미한다.한편, 여기서 [math(A_{나}^n)]은 [math(n)]이 3 이상일 때 영행렬이 되는데, 이것은 그래프 (나)에서 어떤 정점에서 3 step을 이동하여 다른 정점으로 이동할 수 있는 방법이 전혀 없음을 의미한다.
5. 특수한 인접행렬
-
단위행렬
어떤 그래프의 인접행렬이 단위행렬이라면 각 정점에 대해 자기 자신과 연결되는 간선만 존재하는 그래프이다. 이때 몇 step이든 간에 자기 자신으로만 이동할 수 있고 그 경우의 수는 자기 자신으로만 계속해서 이동하는 경우 1가지뿐이므로 인접행렬의 몇 제곱이든 간에 주대각선의 성분만 1이고 나머지 성분은 모두 0인 단위행렬이 된다. -
영행렬
인접행렬이 영행렬이라는 것은 그래프의 간선이 하나도 없다는 뜻이다. 즉, 어떤 정점에서 자기 자신이든 다른 정점으로든 이동이 전혀 불가능하다는 것을 의미한다. 따라서 몇 step이든 간에 이동 자체가 불가능하므로 인접행렬의 몇 제곱이든 간에 똑같이 영행렬이다. -
주대각선의 성분은 모두 0이고 나머지 성분은 모두 1인 경우
각 정점에서 모든 다른 각 정점으로의 쌍방으로 연결하는 간선이 존재하는 그래프의 인접행렬이다. 정점의 개수가 [math(v)]개일 때 간선의 개수는 [math(\displaystyle\frac{v(v+1)}{2})]개, 모든 성분의 합은 [math(v(v+1))]이다. 인접행렬을 [math(A)]라 하면 [math(A^n)]은 다음과 같다.
[math(A^n=\begin{pmatrix}\displaystyle\frac{(v-1)^n+v-1}{v} & \displaystyle\frac{(v-1)^n-1}{v} & \cdots & \displaystyle\frac{(v-1)^n-1}{v} \\ \displaystyle\frac{(v-1)^n-1}{v} & \displaystyle\frac{(v-1)^n+v-1}{v} & \cdots & \displaystyle\frac{(v-1)^n-1}{v} \\ \vdots & \vdots & \ddots & \vdots \\ \displaystyle\frac{(v-1)^n-1}{v} & \displaystyle\frac{(v-1)^n-1}{v} & \cdots & \displaystyle\frac{(v-1)^n+v-1}{v}\end{pmatrix})] (단, [math(n)]은 짝수)
[math(A^n=\begin{pmatrix}\displaystyle\frac{(v-1)^n+1-v}{v} & \displaystyle\frac{(v-1)^n+1}{v} & \cdots & \displaystyle\frac{(v-1)^n+1}{v} \\ \displaystyle\frac{(v-1)^n+1}{v} & \displaystyle\frac{(v-1)^n+1-v}{v} & \cdots & \displaystyle\frac{(v-1)^n+1}{v} \\ \vdots & \vdots & \ddots & \vdots \\ \displaystyle\frac{(v-1)^n+1}{v} & \displaystyle\frac{(v-1)^n+1}{v} & \cdots & \displaystyle\frac{(v-1)^n+1-v}{v}\end{pmatrix})] (단, [math(n)]은 홀수)
따라서 서로 다른 정점 간에 항상 간선이 있는 그래프에서 같은/다른 정점으로 [math(n)] step 만에 이동하는 경우의 수는 다음과 같다. - n이 짝수, 같은 정점 : [math(\displaystyle\frac{(v-1)^n+v-1}{v})]가지
- n이 짝수, 다른 정점 : [math(\displaystyle\frac{(v-1)^n-1}{v})]가지
- n이 홀수, 같은 정점 : [math(\displaystyle\frac{(v-1)^n+1-v}{v})]가지
- n이 홀수, 다른 정점 : [math(\displaystyle\frac{(v-1)^n+1}{v})]가지
-
주대각선을 포함한 모든 성분이 1인 경우
모든 정점에서 자기 자신을 포함한 모든 정점으로 직접 연결되는 간선이 있는 그래프의 경우이다. 이때의 인접행렬을 [math(A)]라 하고, 정점의 개수를 [math(v)]라고 하면 [math(A^n)]은 모든 성분이 [math(v^{n-1})]인 행렬이다. 따라서 이 그래프에서 어떤 정점이든 한 정점에서 다른 정점으로 [math(n)] step 만에 이동하는 방법의 수는 [math(v^{n-1})]이다. 이것은 중복순열을 이용해서도 쉽게 알 수 있는데, [math(n)] step 동안 중간에 지나는 정점의 개수가 [math(n-1)]이고 자기 자신을 포함한 총 [math(v)]개의 정점 중 아무 것이나 선택할 수 있기 때문이다. -
방향 그래프의 사이클
방향 그래프의 정점 [math(v_1, v_2, ..., v_p)]에 대해서 정점 [math((v_1, v_2), (v_2, v_3), ..., (v_{p-1}, v_p), (v_p, v_1))]이 그 순서대로만 연결된 사이클 형태인 경우 그 인접행렬 [math(A)]는 다음과 같다. (단, [math(v_1, v_2, ..., v_p)] 순서)
[math(A=\begin{pmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & 0 & 0 & \cdots & 0 & 0\end{pmatrix})]
위와 같이 주대각선의 바로 오른쪽 성분만 1이고 나머지 성분은 모두 0인 것을 알 수 있다. 이때 [math(A^n)]은 이 그래프에서 [math(n)] step만큼 이동한 것을 나타내는데, 그 경우의 수는 각 정점 [math(v_i)]에서 [math(v_{i+n})]으로 이동하는 경우 하나뿐이다. 따라서 [math(A_{1,1+n}, A_{2,2+n}, ..., A_{p-1,n-1}, A_{p,n})] 성분의 값만 1이 되고 나머지는 모두 0이 된다. 정점의 개수인 [math(p)] step만큼 이동하는 경우는 각 정점에 대해서 다시 제자리로 돌아오는 한 가지 경우밖에 없으므로 [math(A^p=I)]가 된다. 예를 들어 [math(p=3)]인 경우 인접행렬은 다음과 같다.
[math(A=\begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{pmatrix})]
또한 인접행렬의 제곱, 세제곱은 차례로 다음과 같다. 이때 [math(A^3=I)]이다.
[math(A^2=\begin{pmatrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{pmatrix}, A^3=\begin{pmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix})] -
방향 그래프에서 사이클이 없는 경우
방향 그래프의 정점 [math(v_1, v_2, ..., v_p)]에 대해서 정점 [math((v_1, v_2), (v_2, v_3), ..., (v_{p-1}, v_p))]가 그 순서대로만 연결된 사이클 형태인 경우 그 인접행렬 [math(A)]는 다음과 같다. 사이클인 경우에서 [math((v_p, v_1))]의 간선만 제외한 경우이다. (단, [math(v_1, v_2, ..., v_p)] 순서)
[math(A=\begin{pmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0\end{pmatrix})]
단지 성분 하나만 1에서 0이 되었을 뿐인데 계속 제곱했을 때의 결과는 천지 차이이다. 이때는 [math(v_p)]에서 [math(v_1)]로 이동할 수 없으므로 [math(A^n)]은 [math(A_{1,1+n}, A_{2,2+n}, ..., A_{p-n-1,p-1}, A_{p-n,p})] 성분의 값만 1이 되고 나머지는 모두 0이 된다. step 수가 가장 큰 경우는 [math(v_1)]에서 [math(v_p)]로 이동하는 경우이고 이때의 step 수는 [math(p-1)]이므로, [math(A^p)]부터는 반드시 영행렬이다. 예를 들어 [math(p=3)]인 경우 [math(A, A^2, A^3)]은 각각 다음과 같고, [math(A^3)]부터 영행렬이 된다.
[math(A=\begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0\end{pmatrix}, A^2=\begin{pmatrix}0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{pmatrix}, A^3=\begin{pmatrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{pmatrix})]