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

جدول چند مهره در جایگشت بر اساس مختصات طی شده

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

تعریف

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

$\pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace$

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

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

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

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

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

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

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

$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}}.$

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

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

منابع

• Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Vol. 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». در دانشنامهٔ ویکی‌پدیای انگلیسی.