Ternyata matriks permutasi

Misalkan A \in \mathbb{R}^{n \times n} merupakan matriks yang invertible yang entri-entrinya merupakan bilangan bulat tak negatif. Andaikan bahwa himpunan

\displaystyle \bigcup_{i=1}^\infty \{A^i\}

merupakan himpunan berhingga. Tunjukkan bahwa A merupakan matriks permutasi.

Solusi.

Karena himpunan tersebut berhingga, terdapat dua bilangan asli berbeda i>j sehingga A^i=A^j. Dengan demikian, A^{i-j}=I. Misalkan n merupakan bilangan asli terkecil demikian sehingga A^n=I. Mudah dilihat bahwa \displaystyle \bigcup_{i=1}^\infty \{A^i\}=\{I,A,A^2,\dots,A^{n-1}\}.

Sekarang, karena \det(A^n)=I, maka \det(A)=\pm 1. Dengan demikian, terdapat permutasi \sigma dari 1,2,\dots,n demikian sehingga \prod_i a_{i \sigma(i)}. Dengan demikian, terdapat matriks permutasi P dan matriks tak nol dan matriks berentri bulat tak negatif A_1 demikian sehingga A=P+A_1.

Perhatikan bahwa terdapat bilangan asli m dan n demikian sehingga A^m=P^n=I. Kedua ruas dari persamaan A=P+A_1 dipangkatkan mn sehingga diperoleh

A^{mn}=P^{mn}+P^{mn-1}A_1+\dots+A_1^{mn}

I=I+P^{mn-1}A_1+\dots+A_1^{mn}

O=P^{mn-1}A_1+\underbrace{\dots+A_1^{mn}}_{\text{semua entrinya} \, \ge 0}

sehingga semua entri P^{mn-1}A_1 haruslah bernilai 0. Namun P^{mn-1} merupakan matriks permutasi sehingga hanya mengacak urutan baris A_1. Dengan demikian, haruslah A_1=O.

Jadi, diperoleh bahwa A=P+O=P untuk suatu matriks permutasi P.

Refleksi.

Ini soal imut-imut tidak bersalah. Saya suka.

 

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s