ماتریس جایگشت

در ریاضیات، بخصوص در نظریه ماتریس‌ها، یک ماتریس جایگشت (به انگلیسی: Permutation Matrix)، ماتریسی مربعی مبنای دویی است که در هر سطر و ستون آن دقیقاً یک درایه 1 داشته و بقیه درایه ها 0 باشند. هر ماتریس با این خصوصیت چون ${\displaystyle P}$، نماینده جایگشت ${\displaystyle m}$ عنصر است و زمانی که در ماتریسی چون ${\displaystyle A}$ ضرب شد، باعث جایگشت سطور (اگر ضرب به صورت ${\displaystyle PA}$ باشد) یا ستون ها (اگر ضرب به صورت ${\displaystyle AP}$ باشد) ی ماتریس ${\displaystyle A}$ می شود.

تعریف

فرض کنید جایگشت دلخواه ${\displaystyle \pi }$ از ${\displaystyle m}$ عنصر داده شده باشد:

${\displaystyle \pi$ :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace }

که می توان آن را به صورت زیر نمایش داد:

${\displaystyle {\begin{pmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{pmatrix}},}$

دو راه برای نظیر کردن یک ماتریس به چنین جایگشتی وجود دارد؛ از یک ماتریس ${\displaystyle m\times m}$ همانی ${\displaystyle I_{m}}$ شروع کرده و بر اساس ${\displaystyle \pi }$ سطر ها یا ستون های آن را جایگشت دهیم. هردو روش به عنوان تعریف ماتریس جایگشت در متون ظاهر شده اند و خواص بیان شده در یک نمایش را می توان به راحتی تبدیل به نمایش های دیگر کرد. در این مقاله تنها با یکی از این نمایش ها سروکار خواهیم داشت و تنها زمانی که نیاز باشد به تفاوت دو نمایش اشاره می شود.

ماتریس ${\displaystyle m\times m}$ جایگشت ${\displaystyle P_{\pi }=(p_{ij})}$ با جایگشت ستون های ماتریس همانی ${\displaystyle I_{m}}$ بدست می آید، یعنی برای هر ${\displaystyle i}$ اگر ${\displaystyle j=\pi (i)}$ آنگاه ${\displaystyle p_{ij}=1}$ در غیر این صورت ${\displaystyle p_{ij}=1}$. در این مقاله از چنین جایگشتی به نمایش ستونی یاد می شود.[1] از آنجایی که درایه های سطر ${\displaystyle i}$ ام همگی 0 هستند به جز یک درایه 1 در ستون ${\displaystyle \pi (i)}$، می توان نوشت:

${\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}},}$

که در آن ${\displaystyle e_{j}}$، بردار پایه استاندارد است که نشانگر بردار سطری به طول ${\displaystyle m}$ با موقعت ${\displaystyle j}$ ام 1 است که درایه های دیگر آن 0 اند.[2]

به عنوان مثال، ماتریس جایگشت ${\displaystyle P_{\pi }}$ متناظر با جایگشت ${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}}$ به این صورت است:

${\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.}$

همانگونه که مشاهده می کنید، ستون ${\displaystyle j}$ ام ماتریس همانی ${\displaystyle I_{5}}$، اکنون به صورت ستون ${\displaystyle \pi (j)}$ ام ${\displaystyle P_{\pi }}$ ظاهر شده است.

نمایش های دیگر از جایگشت سطر های ماتریس ${\displaystyle I_{m}}$ بدست می آیند، یعنی برای هر ${\displaystyle j}$، اگر ${\displaystyle i=\pi (i)}$ آنگاه ${\displaystyle p_{ij}=1}$ و در غیر این صورت ${\displaystyle p_{ij}=0}$. به نمایش اخیر نمایش سطری می گویند.

پانویس

1. این عبارت استاندارد نیست. بسیاری از مؤلفان یک نمایش را جوری انتخاب می کنند که با بقیه نمادگذاری های معرفی شده از سوی آن ها سازگاری داشته باشد، بنابر این در حالت کلی نیازی به ارائه اسم برای چنین نمایشی وجود ندارد.
2. Brualdi (2006) p.2

منابع

• Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.
• Joseph, Najnudel; Ashkan, Nikeghbali (2010), The Distribution of Eigenvalues of Randomized Permutation Matrices, arXiv:1005.0402, Bibcode:2010arXiv1005.0402N

• مشارکت‌کنندگان ویکی‌پدیا. «Permutation Matrix». در دانشنامهٔ ویکی‌پدیای انگلیسی.