앞서 우리는 행렬의 곱셈만으로 (역행렬도 사용하기는 했지만) 일차방정식의 해를 구했고, 마르코프 체인에도 응용해보았다. 이제 마르코프 체인에서 전이행렬을 거듭제곱하는 경우를 생각해보자.

한 전이행렬이 있는데, 이 전이행렬이 다루는 상태의 개수는 10,000개이다. 그리고 이 전이행렬은 10,000개의 상태에서 10,000개의 상태로의 전이 확률을 값으로 갖는다. 10,000행 10,000열짜리 행렬을 거듭제곱한다면 생각보다 쉬운 작업은 아닐 것이다. 특히 원소가 0이 아닌 행렬이라면 곱해야 하는 원소가 많아 계산량이 많아진다. 그리고 만약 행과 열의 수가 각 1,000,000개가 된다면 이제는 복잡한 계산 문제로 바뀐다. 행렬의 곱셈 자체는 그리 어려운 것은 아니지만, 실생활의 문제를 다루다 보면 행과 열이 큰 행렬을 곱하게 되는데, 이는 종종 어려운 문제가 된다. 어떻게 하면 잘 해결할 수 있을까?

만약 행렬에 0이 아주 많다면, 다르게 표현해서 값이 아주 희박(sparse)하다면 의외로 쉽게 곱셈할 수 있다. 곱하는 두 행렬에서 한 행렬이라도 원소가 0이면 계산하지 않아도 결과가 0이라는 것을 쉽게 알 수 있기 때문이다. 이 부분에서 여러분은 아마도 2장 초반에 다룬 다양한 행렬의 종류 가운데 영행렬, 대각행렬, 상삼각행렬, 하삼각행렬 등을 떠올렸을 것이다. 바로 0이 많이 포함된 행렬들이다. 행렬의 곱셈에서 이렇게 0이 많은 행렬을 활용한다면 아무리 큰 행렬이라도 생각보다 단순하게 계산할 수 있다.