جایگشت‌ها

موضوع اصلی این کتاب معمولاً به نام جبر خطی شناخته می‌شود. با این حال، در سه بخش آخر، تأکید بر چیزی به نام جبر چندخطی بود. تعیین دقیق مرز میان این دو موضوع دشوار است. از آنجا که در هر صورت، هر دو موضوع بسیار گسترده هستند، عملی نخواهد بود که بخواهیم بررسی دقیقی از هر دو را در یک مجلد بگنجانیم. همچنین مطلوب نیست که جبر خطی را در حالت کاملاً خالص آن مورد بحث قرار دهیم؛ افزودن حتی بخش کوچکی از نظریه چندخطی (مانند آنچه در دیدگاه مدرن حاصل‌ضرب‌های تانسوری و دترمینان‌ها دخیل است) قلمرو کاربرد نظریه خطی را به طرز خوشایندی و نامتناسب با تلاش صرف‌شده گسترش می‌دهد. بر این اساس، پیشنهاد می‌کنیم که به مطالعه جبر چندخطی ادامه دهیم؛ قصد ما ترسیم خطی کم و بیش مستقیم میان آنچه از پیش می‌دانیم و حقایق بنیادی درباره دترمینان‌هاست. با در نظر داشتن این موضوع، سه بخش را به بحث درباره برخی حقایق ساده در مورد ترکیبیات اختصاص خواهیم داد؛ ارتباط میان آن حقایق و جبر چندخطی بلافاصله پس از آن بحث آشکار خواهد شد.

منظور ما از یک جایگشت از اعداد صحیح بین $1$ و $k$ (شامل خود آن‌ها) یک تبدیل یک‌به‌یک است که به هر یک از چنین اعداد صحیحی، عدد صحیح دیگری (یا احتمالاً همان عدد) را نسبت می‌دهد. اینکه بگوییم تبدیل $\pi$ یک‌به‌یک است، البته به این معناست که اگر $\pi (1),\dots ,\pi (k)$ اعداد صحیحی باشند که $\pi$ به ترتیب به $1,\dots ,k$ نسبت می‌دهد، آنگاه $\pi (i)=\pi (j)$ تنها در صورتی می‌تواند رخ دهد که $i=j$ باشد. از آنجا که این امر دلالت بر آن دارد که هر دو مجموعه $\{1,\dots ,k\}$ و $\{\pi (1),\dots ,\pi (k)\}$ دقیقاً از $k$ عنصر تشکیل شده‌اند، نتیجه می‌شود که آن‌ها دقیقاً از عناصر یکسانی تشکیل شده‌اند. از این رو، به نوبه خود، استنتاج می‌کنیم که یک جایگشت $\pi$ از مجموعه $\{1,\dots ,k\}$ آن مجموعه را روی خودش می‌نگارد، یعنی اینکه اگر $1\le j\le k$ باشد، آنگاه حداقل یک $i$ (و در واقع، دقیقاً یکی) وجود دارد به طوری که $\pi (i)=j$ باشد. تعداد کل اعداد صحیح مورد بحث، یعنی $k$ ، در سراسر بحث پیش رو ثابت در نظر گرفته خواهد شد.

نظریه جایگشت‌ها، مانند هر چیز دیگری، با خیره شدن دقیق به برخی مثال‌های غیربدیهی به بهترین وجه درک می‌شود. با این حال، پیش از ارائه هرگونه مثال، ابتدا به برخی از امور کلی که می‌توان با جایگشت‌ها انجام داد اشاره خواهیم کرد؛ بدین وسیله، مثال‌ها نه تنها مفهوم بنیادی، بلکه ویژگی‌های اساسی آن را نیز نشان خواهند داد.

اگر $\sigma$ و $\tau$ جایگشت‌های دلخواهی باشند، یک جایگشت (که با $\sigma \tau$ نشان داده می‌شود) را می‌توان با نوشتن $$(\sigma \tau )(i)=\sigma (\tau (i))$$ به ازای هر $i$ تعریف کرد. برای اثبات اینکه $\sigma \tau$ واقعاً یک جایگشت است، توجه کنید که اگر $(\sigma \tau )(i)=(\sigma \tau )(j)$ باشد، آنگاه $\tau (i)=\tau (j)$ است (زیرا $\sigma$ یک‌به‌یک است)، و بنابراین $i=j$ است (زیرا $\tau$ یک‌به‌یک است). جایگشت $\sigma \tau$ را حاصل‌ضرب جایگشت‌های $\sigma$ و $\tau$ می‌نامند. باید گفت که ترتیب مهم است. به طور کلی $\sigma \tau \ne \tau \sigma$ است، یا به عبارت دیگر، ضرب جایگشت‌ها جابجایی نیست.

ضرب جایگشت‌ها شرکت‌پذیر است؛ یعنی اگر $\pi$ ، $\sigma$ و $\tau$ جایگشت باشند، آنگاه برای اثبات این موضوع، باید نشان دهیم که $$((\pi \sigma )\tau )(i)=(\pi (\sigma \tau ))(i)$$ به ازای هر $i$ برقرار است. اثبات شامل چندین بار کاربرد تعریف حاصل‌ضرب است، به شرح زیر: $$((\pi \sigma )\tau )(i)=(\pi \sigma )(\tau (i))=\pi (\sigma (\tau (i))),$$ و $$(\pi (\sigma \tau ))(i)=\pi ((\sigma \tau )(i))=\pi (\sigma (\tau (i))).$$ 

با توجه به این نتیجه، ممکن است و خواهیم توانست پرانتزها را در نوشتن حاصل‌ضرب سه یا چند جایگشت حذف کنیم. این نتیجه همچنین ما را قادر می‌سازد تا قوانین بدیهی توان‌ها را اثبات کنیم. توان‌های یک جایگشت $\pi$ به صورت استقرایی با نوشتن ${\pi }^1=\pi$ و ${\pi }^{p+1}=\pi \cdot {\pi }^p$ برای همه $p=1,2,3,\dots$ تعریف می‌شوند؛ قانون شرکت‌پذیری ایجاب می‌کند که ${\pi }^p\cdot {\pi }^q={\pi }^{p+q}$ و $({\pi }^p{)}^q={\pi }^{pq}$ برای همه $p$ ها و $q$ ها برقرار باشد. توجه کنید که هر دو توان از یک جایگشت با یکدیگر جابجا می‌شوند، یعنی ${\pi }^p\cdot {\pi }^q={\pi }^q\cdot {\pi }^p$ .

ساده‌ترین جایگشت، جایگشت همانی است (که با $ϵ$ نشان داده می‌شود)؛ این جایگشت با $ϵ(i)=i$ به ازای هر $i$ تعریف می‌شود. اگر $\pi$ یک جایگشت دلخواه باشد، آنگاه یا به عبارت دیگر، ضرب در $ϵ$ هر جایگشتی را بدون تغییر باقی می‌گذارد. اثبات این امر سرراست است؛ برای هر $i$ داریم $$(ϵ\pi )(i)=ϵ(\pi (i))=\pi (i)$$ و $$(\pi ϵ)(i)=\pi (ϵ(i))=\pi (i).$$ 

جایگشت $ϵ$ از دیدگاه ضرب، مانند عدد $1$ رفتار می‌کند. در قیاس با قرارداد عددی معمول، توان صفرم هر جایگشت $\pi$ با نوشتن ${\pi }^0=ϵ$ تعریف می‌شود.

اگر $\pi$ یک جایگشت دلخواه باشد، آنگاه یک جایگشت وجود دارد (که با ${\pi }^{-1}$ نشان داده می‌شود) به طوری که برای تعریف ${\pi }^{-1}(j)$ ، که البته در آن $1\le j\le k$ است، $i$ یکتایی را بیابید به طوری که $\pi (i)=j$ باشد، و بنویسید ${\pi }^{-1}(j)=i$ ؛ اعتبار (3) پیامد مستقیم تعاریف است. جایگشت ${\pi }^{-1}$ را معکوس $\pi$ می‌نامند.

فرض کنید ${𝒮}_k$ مجموعه تمام جایگشت‌های اعداد صحیح بین $1$ و $k$ باشد. آنچه تاکنون اثبات کرده‌ایم این است که می‌توان عملیات ضرب را برای عناصر ${𝒮}_k$ به گونه‌ای تعریف کرد که (1) ضرب شرکت‌پذیر باشد، (2) یک عنصر همانی وجود داشته باشد، یعنی عنصری که ضرب در آن هر عنصر ${𝒮}_k$ را ثابت نگه دارد، و (3) هر عنصر دارای یک معکوس باشد، یعنی عنصری که حاصل‌ضرب آن با عنصر داده‌شده برابر با همانی باشد. مجموعه‌ای که در شرایط (1) تا (3) صدق کند، نسبت به مفهوم حاصل‌ضربی که آن شرایط به آن اشاره دارند، یک گروه نامیده می‌شود؛ مجموعه ${𝒮}_k$ ، به طور خاص، گروه متقارن از درجه $k$ نامیده می‌شود. توجه کنید که اعداد صحیح $1,\dots ,k$ می‌توانستند با هر $k$ شیء متمایز دیگری جایگزین شوند بدون اینکه تأثیری بر هیچ‌یک از مفاهیم تعریف‌شده در بالا داشته باشد؛ این تغییر صرفاً امری نمادین خواهد بود.