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

توسط علی رضا نقش نیلچی | یکشنبه بیست و ششم بهمن ۱۳۹۹ | 21:0

از ویکیپدیا، دانشنامه آزاد

در ریاضیات ، به ویژه در تئوری ماتریس ، ماتریس جایگشت یک ماتریس باینری مربع است که دقیقاً یک ورودی از هر ردیف 1 و هر ستون و 0 در جای دیگر دارد. هر ماتریسی از این دست ، مثلاً P ، نشان دهنده یک جایگزینی از عناصر m است و ، هنگامی که برای ضرب ماتریس دیگری استفاده می شود ، مثلاً A ، منجر به تغییر سطرها (هنگام پیش ضرب ، تشکیل PA ) یا ستون ها (هنگام پس از ضرب ، به شکل AP ) از ماتریس .

فهرست

تعریف [ ویرایش ]

با توجه به یک جایگشت π از متر عناصر،

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

به صورت دو خطی توسط

${\ start {pmatrix} 1 & 2 & \ cdots & m \\\ pi (1) & \ pi (2) & \ cdots & \ pi (m) \ end {pmatrix}} ،$

دو روش طبیعی برای ارتباط دادن جایگشت با ماتریس جایگشت وجود دارد. یعنی، با شروع متر × متر ماتریس ، من متر ، یا پس و پیش کردن ستون ها و یا تغییر دادن ردیف، با توجه به π . هر دو روش تعریف ماتریس های جایگشت در ادبیات ظاهر می شود و خصوصیات بیان شده در یک نمایش را می توان به راحتی به نمایش دیگر تبدیل کرد. این مقاله در درجه اول فقط به یکی از این بازنمایی ها می پردازد و مقاله دیگر فقط در مواردی ذکر می شود که تفاوتی وجود داشته باشد.

m × m جایگشت ماتریس P π = ( P IJ ) به دست آمده توسط permuting ستون از ماتریس Mi ، این است که، برای هرI ، P ij= 1 اگر j= π (i ) و P ij = 0 در غیر این صورت، در این مقاله به عنوان نمایش ستون معرفی می شود . [1] از آنجا که ورودی های سطر i همه 0 هستند با این تفاوت که a 1 در ستون π ( i ) ظاهر می شود ، ممکن است بنویسیم

$P _ {\ pi} = {\ start {bmatrix} {\ mathbf e} _ {{\ pi (1)}} \\ {\ mathbf e} _ {{\ pi (2)}} \\\ vdots \\ {\ mathbf e} _ {{\ pi (m)}} \ end {bmatrix}} ،$

جایی که ${\ mathbf e} _ {j}$ ، یک بردار مبنای استاندارد ، بردار ردیفی به طول m را نشان می دهد که 1 در موقعیت j و 0 در هر موقعیت دیگر است. [2]

به عنوان مثال ، ماتریس جایگشت P π مربوط به جایگشت است ${\ displaystyle \ pi = {\ start {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \ end {pmatrix}}}$ است

$P _ {\ pi} = {\ start {bmatrix} {\ mathbf {e}} _ {{\ pi (1)}} \\ {\ mathbf {e}} _ {{\ pi (2)}} \ \ {\ mathbf {e}} _ {{\ pi (3)}} \\ {\ mathbf {e}} _ {{\ pi (4)}} \\ {\ mathbf {e}} _ {{\ pi (5)}} \ end {bmatrix}} = {\ start {bmatrix} {\ mathbf {e}} _ {{1}} \\ {\ mathbf {e}} _ {{4}} \\ {\ mathbf {e}} _ {{2}} \\ {\ mathbf {e}} _ {{5}} \\ {\ mathbf {e}} _ {{3}} \ end {bmatrix}} = {\ start {bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \ 0 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \ end {bmatrix}}$

مشاهده کنید که ستون j ماتریس هویت I 5 اکنون به عنوان ستون π ( j ) هفتم P π ظاهر می شود .

نمایش دیگر که با جایگزینی ردیف های ماتریس هویت I m بدست می آید ، یعنی برای هر j ، p ij = 1 اگر i = π ( j ) و در غیر این صورت p ij = 0 باشد ، به عنوان نمایش ردیف شناخته می شود .

خصوصیات [ ویرایش ]

نمایش ستون یک ماتریس تغییر در کل این بخش استفاده می شود ، مگر اینکه در موارد دیگری مشخص شده باشد.

ضرب کردن $P _ {{\ pi}}$ بار یک بردار ستون g ردیف های بردار را تغییر می دهد:

$P _ {\ pi} {\ mathbf {g}} = {\ start {bmatrix} {\ mathbf {e}} _ {{\ pi (1)}} \\ {\ mathbf {e}} _ {{\ pi (2)}} \\\ vdots \\ {\ mathbf {e}} _ {{\ pi (n)}} \ end {bmatrix}} {\ start {bmatrix} g_ {1} \\ g_ {2} \\\ vdots \\ g_ {n} \ end {bmatrix}} = {\ start {bmatrix} g _ {{\ pi (1)}} \\ g _ {{\ pi (2)}} \\\ vdots \ \ g _ {{\ pi (n)}} \ end {bmatrix}}.$

استفاده مکرر از این نتیجه نشان می دهد که اگر M یک ماتریس مناسب باشد ، محصول ، ${\ displaystyle P _ {\ pi} M}$ فقط جایگزینی ردیف های M است . با این حال ، با مشاهده آن

${\ displaystyle P _ {\ pi} \ mathbf {e} _ {k} ^ {\ mathsf {T}} = \ mathbf {e} _ {\ pi ^ {- 1} (k)} ^ {\ mathsf {T }}}$

برای هر k نشان می دهد که جایگزینی ردیف ها توسط π -1 داده می شود . ( ${\ displaystyle M ^ {\ mathsf {T}}}$ است ترانهاده ماتریس M .)

همانطور که ماتریس جایگشت ماتریس متعامد است (به عنوان مثال ، ${\ displaystyle P _ {\ pi} P _ {\ pi} ^ {\ mathsf {T}} = I}$ ) ، ماتریس معکوس وجود دارد و می توان آنرا نوشت

${\ displaystyle P _ {\ pi} ^ {- 1} = P _ {\ pi ^ {- 1}} = P _ {\ pi} ^ {\ mathsf {T}}.}$

ضرب یک بردار ردیف h بار $P _ {{\ pi}}$ ستون های بردار را تغییر می دهد:

${\ mathbf {h}} P _ {\ pi} = {\ start {bmatrix} h_ {1} \؛ h_ {2} \؛ \ dots \؛ h_ {n} \ end {bmatrix}} {\ start {bmatrix } {\ mathbf {e}} _ {{\ pi (1)}} \\ {\ mathbf {e}} _ {{\ pi (2)}} \\\ vdots \\ {\ mathbf {e}} _ {{\ pi (n)}} \ end {bmatrix}} = {\ start {bmatrix} h _ {{\ pi ^ {{- 1}} (1)}} \؛ h _ {{\ pi ^ {{ -1}} (2)}} \؛ \ نقطه \؛ h _ {{\ pi ^ {{- 1}} (n)}} \ پایان {bmatrix}}$

باز هم ، استفاده مکرر از این نتیجه نشان می دهد که پس از ضرب یک ماتریس M در ماتریس جایگشت P π ، یعنی MP π ، منجر به جا به جایی ستون های M می شود . همچنین توجه داشته باشید که

${\ displaystyle \ mathbf {e} _ {k} P _ {\ pi} = \ mathbf {e} _ {\ pi (k)}.}$

با توجه به دو تغییر مکان π و σ از عناصر m ، ماتریس های جایگشت مربوطه P π و P σ بر روی بردارهای ستون عمل می کنند با

${\ displaystyle P _ {\ sigma} P _ {\ pi} \، \ mathbf {g} = P _ {\ pi \، \ circ \، \ sigma} \، \ mathbf {g}.}$

همان ماتریس هایی که بر روی بردارهای ردیف عمل می کنند (یعنی بعد از ضرب) مطابق با همان قاعده تشکیل می شوند

${\ displaystyle \ mathbf {h} P _ {\ sigma} P _ {\ pi} = \ mathbf {h} P _ {\ pi \ ، \ circ \ ، \ sigma}.}$

برای اینکه روشن شود ، فرمول های فوق از پیشوند علامت برای ترکیب جایگشت استفاده می کنند ، یعنی

${\ displaystyle (\ pi \ ، \ circ \ ، \ sigma) (k) = \ pi \ چپ (\ sigma (k) \ راست).}$

اجازه دهید ${\ displaystyle Q _ {\ pi}}$ ماتریس جایگزینی مربوط به π در نمایش ردیف آن باشد. خصوصیات این نمایش را می توان از ویژگی های نمایش ستون از آن زمان تعیین کرد ${\ displaystyle Q _ {\ pi} = P _ {\ pi} ^ {\ mathsf {T}} = P _ {{\ pi} ^ {- 1}}.}$ به خصوص،

${\ displaystyle Q _ {\ pi} \ mathbf {e} _ {k} ^ {\ mathsf {T}} = P _ {{\ pi} ^ {- 1}} \ mathbf {e} _ {k} ^ {\ mathsf {T}} = \ mathbf {e} _ {(\ pi ^ {- 1}) ^ {- 1} (k)} ^ {\ mathsf {T}} = \ mathbf {e} _ {\ pi ( k)} ^ {\ mathsf {T}}.}$

از این نتیجه است که

${\ displaystyle Q _ {\ sigma} Q _ {\ pi} \، \ mathbf {g} = Q _ {\ sigma \، \ circ \، \ pi} \، \ mathbf {g}.}$

به طور مشابه ،

${\ displaystyle \ mathbf {h} \، Q _ {\ sigma} Q _ {\ pi} = \ mathbf {h} \، Q _ {\ sigma \، \ circ \، \ pi}.}$

گروه ماتریکس [ ویرایش ]

اگر (1) نشان دهنده جایگشت هویت، سپس P (1) است ماتریس .

بگذارید S n نشانگر گروه متقارن یا گروه جایگشت ها در {1،2 ، ... ، n } باشد. از آنجا که n وجود دارد! جایگشت ، n وجود دارد ! ماتریس های جایگشت. توسط فرمول های فوق، N × N ماتریس جایگشت یک شکل گروه تحت عمل ضرب ماتریس با ماتریس هویت به عنوان عنصر هویت .

نقشه S n → A ⊂ GL ( n ، Z 2 ) نمایشی صادقانه است . بنابراین ، | الف | = n ! .

ماتریس تصادفی دو برابر [ ویرایش ]

ماتریس جایگشت خود یک ماتریس تصادفی مضاعف است ، اما در تئوری این ماتریس ها نیز نقش ویژه ای دارد. Birkhoff-فون نویمان قضیه می گوید که هر ماتریس واقعی مضاعف تصادفی است ترکیب محدب از ماتریس جایگشت از همان نظم و ماتریس جایگشت دقیقا نقاط شدید از مجموعه ای از ماتریس مضاعف تصادفی. یعنی پلی پتوپ Birkhoff ، مجموعه ای از ماتریس های تصادفی مضاعف ، بدنه محدب مجموعه ماتریس های جایگشت است. [3]

خصوصیات جبری خطی [ ویرایش ]

اثری از ماتریس جایگشت تعداد است نقطه ثابت از جایگشت. اگر جایگشت دارای نقاط ثابت باشد ، بنابراین می توان آن را به صورت چرخه به صورت π = ( a 1 ) ( a 2 ) ... ( a k ) σ نوشت که در آن σ هیچ نقطه ثابتی وجود ندارد ، سپس e a 1 ، e a 2 ، ...، K هستند بردارهای ویژه ماتریس جایگشت.

برای محاسبه مقادیر ویژه ماتریس جایگشت ${\ displaystyle P _ {\ sigma}}$ ، نوشتن $\ سیگما$ به عنوان یک محصول از چرخه ها ، مثلا ، ${\ displaystyle \ sigma = C_ {1} C_ {2} \ cdots C_ {t}}$ . اجازه دهید طول مربوط به این چرخه ها برابر باشد ${\ displaystyle l_ {1} ، l_ {2} ... l_ {t}}$ ، و اجازه دهید ${\ displaystyle R_ {i} (1 \ leq i \ leq t)}$ مجموعه ای از راه حل های پیچیده باشد ${\ displaystyle x ^ {l_ {i}} = 1}$ . اتحاد همه $R_ {i}$ s مجموعه مقادیر ویژه ماتریس جایگشت مربوطه است. تعدد هندسی هر یک از مقادیر ویژه برابر است با تعداد $R_ {i}$ که حاوی آن است. [4]

از تئوری گروه می دانیم که هر جایگزینی ممکن است به عنوان ضرب جابجایی نوشته شود . بنابراین ، هر فاکتور P ماتریس جایگشت به عنوان ضربی از ماتریس های مقدماتی ردیف ، هر کدام دارای تعیین کننده 1 هستند. بنابراین تعیین کننده ماتریس جایگزینی P فقط امضای جایگشت مربوطه است.

مثالها [ ویرایش ]

تغییر سطرها و ستون ها [ ویرایش ]

هنگامی که یک ماتریس جایگزینی P از سمت چپ با یک ماتریس M ضرب می شود تا PM ایجاد کند ، آن ردیفهای M را تغییر می دهد (در اینجا عناصر بردار ستون) ،
وقتی P از راست با M ضرب می شود تا MP ایجاد کند ، ستون های M (در اینجا عناصر بردار ردیف):

P * (1،2،3،4) T = (4،1،3،2) T

(1،2،3،4) * P = (2،4،3،1)

جابجایی های ردیف ها و ستون ها به عنوان مثال بازتاب (به زیر را ببینید) و جایگشت های حلقوی (به ماتریس جایگشت چرخه ای مراجعه کنید ).

نشان دادنبازتاب

جایگشت ردیف ها [ ویرایش ]

ماتریس جایگشت P π مربوط به جایگشت: $\ pi = {\ start {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \ end {pmatrix}} ،$ است

با توجه به بردار g ،

$P _ {\ pi} {\ mathbf {g}} = {\ start {bmatrix} {\ mathbf {e}} _ {{\ pi (1)}} \\ {\ mathbf {e}} _ {{\ pi (2)}} \\ {\ mathbf {e}} _ {{\ pi (3)}} \\ {\ mathbf {e}} _ {{\ pi (4)}} \\ {\ mathbf {e }} _ {{\ pi (5)}} \ end {bmatrix}} {\ start {bmatrix} g_ {1} \\ g_ {2} \\ g_ {3} \\ g_ {4} \\ g_ { 5} \ end {bmatrix}} = {\ start {bmatrix} g_ {1} \\ g_ {4} \\ g_ {2} \\ g_ {5} \\ g_ {3} \ end {bmatrix}}.$

توضیح [ ویرایش ]

یک ماتریس جایگشت همیشه در فرم وجود دارد

${\ start {bmatrix} {\ mathbf {e}} _ {{a_ {1}}} \\ {\ mathbf {e}} _ {{a_ {2}}} \\\ vdots \\ {\ mathbf { e}} _ {{a_ {j}}} \\\ end {bmatrix}}$

که در آن E i نشان دهندهi هفتم بردار پایه (به عنوان یک ردیف) برای R j را ، و که در آن

${\ start {bmatrix} 1 & 2 & \ ldots & j \\ a_ {1} & a_ {2} & \ ldots & a_ {j} \ end {bmatrix}}$

است جایگشت شکل ماتریس جایگشت است.

اکنون ، در انجام ضرب ماتریس ، اساساً یک جایگشت نقطه از هر ردیف از ماتریس اول با هر ستون از دوم را تشکیل می دهد. در این نمونه ، ما محصول نقطه هر ردیف از این ماتریس را با بردار عناصری که می خواهیم تغییر دهیم ، تشکیل می دهیم. به عنوان مثال ، v = ( g 0 ، ... ، g 5 ) T ،

e a i · v = g a i

بنابراین ، محصول ماتریس جایگشت با بردار v در بالا ، یک بردار به شکل ( g a 1 ، g a 2 ، ...، g a j ) خواهد بود ، و این پس یک جایگشت v است زیرا ما گفته اند که فرم جایگشتی است

${\ start {pmatrix} 1 & 2 & \ ldots & j \\ a_ {1} & a_ {2} & \ ldots & a_ {j} \ end {pmatrix}}.$

بنابراین ، ماتریس های جایگشت به ترتیب ترتیب عناصر در بردارهای ضرب شده با آنها را تغییر می دهند.

فرمهای محدود [ ویرایش ]

آرایه Costas ، یک ماتریس تغییر مکان که در آن بردارهای جابجایی بین ورودی ها همه مشخص هستند
n-queens puzzle ، یک ماتریس جایگزینی که در آن حداکثر یک ورودی در هر قطر و مورب وجود دارد

همچنین به [ ویرایش ] مراجعه کنید

منبع

https://en.wikipedia.org/wiki/Permutation_matrix

مشخصات وب

در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.
09132003030

ریاضیات

آموزش ریاضی