Permutation matrix

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Permutation matrix - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"35647a64-33a4-4cba-8617-93b7de6b029e","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Permutation_matrix","wgTitle":"Permutation matrix","wgCurRevisionId":1242522638,"wgRevisionId":1242522638,"wgArticleId":238849,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Use American English from January 2019","All Wikipedia articles written in American English","Matrices","Permutations","Sparse matrices"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Permutation_matrix","wgRelevantArticleId":238849,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[], "wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q851512","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false, "wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups", "ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Permutation matrix - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Permutation_matrix"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Permutation_matrix&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Permutation_matrix"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Permutation_matrix rootpage-Permutation_matrix skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Permutation+matrix" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Permutation+matrix" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Permutation+matrix" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Permutation+matrix" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-The_two_permutation/matrix_correspondences" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#The_two_permutation/matrix_correspondences"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>The two permutation/matrix correspondences</span> </div> </a> <ul id="toc-The_two_permutation/matrix_correspondences-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Permutation_matrices_permute_rows_or_columns" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Permutation_matrices_permute_rows_or_columns"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Permutation matrices permute rows or columns</span> </div> </a> <ul id="toc-Permutation_matrices_permute_rows_or_columns-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_transpose_is_also_the_inverse" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#The_transpose_is_also_the_inverse"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>The transpose is also the inverse</span> </div> </a> <ul id="toc-The_transpose_is_also_the_inverse-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Multiplying_permutation_matrices" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Multiplying_permutation_matrices"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Multiplying permutation matrices</span> </div> </a> <ul id="toc-Multiplying_permutation_matrices-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Matrix_group" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Matrix_group"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Matrix group</span> </div> </a> <ul id="toc-Matrix_group-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Doubly_stochastic_matrices" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Doubly_stochastic_matrices"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Doubly stochastic matrices</span> </div> </a> <ul id="toc-Doubly_stochastic_matrices-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Linear-algebraic_properties" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Linear-algebraic_properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Linear-algebraic properties</span> </div> </a> <ul id="toc-Linear-algebraic_properties-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Restricted_forms" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Restricted_forms"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Restricted forms</span> </div> </a> <ul id="toc-Restricted_forms-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Permutation matrix</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 28 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-28" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">28 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%85%D8%B5%D9%81%D9%88%D9%81%D8%A9_%D8%AA%D8%A8%D8%AF%D9%8A%D9%84%D9%8A%D8%A9" title="مصفوفة تبديلية – Arabic" lang="ar" hreflang="ar" data-title="مصفوفة تبديلية" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Matriu_permutaci%C3%B3" title="Matriu permutació – Catalan" lang="ca" hreflang="ca" data-title="Matriu permutació" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Permuta%C4%8Dn%C3%AD_matice" title="Permutační matice – Czech" lang="cs" hreflang="cs" data-title="Permutační matice" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Permutationsmatrix" title="Permutationsmatrix – German" lang="de" hreflang="de" data-title="Permutationsmatrix" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%A0%CE%AF%CE%BD%CE%B1%CE%BA%CE%B1%CF%82_%CE%BC%CE%B5%CF%84%CE%B1%CE%B8%CE%AD%CF%83%CE%B5%CF%89%CE%BD" title="Πίνακας μεταθέσεων – Greek" lang="el" hreflang="el" data-title="Πίνακας μεταθέσεων" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Matriz_permutaci%C3%B3n" title="Matriz permutación – Spanish" lang="es" hreflang="es" data-title="Matriz permutación" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Permuta_matrico" title="Permuta matrico – Esperanto" lang="eo" hreflang="eo" data-title="Permuta matrico" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Permutazio-matrize" title="Permutazio-matrize – Basque" lang="eu" hreflang="eu" data-title="Permutazio-matrize" data-language-autonym="Euskara" data-language-local-name="Basque" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%A7%D8%AA%D8%B1%DB%8C%D8%B3_%D8%AC%D8%A7%DB%8C%DA%AF%D8%B4%D8%AA" title="ماتریس جایگشت – Persian" lang="fa" hreflang="fa" data-title="ماتریس جایگشت" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Matrice_de_permutation" title="Matrice de permutation – French" lang="fr" hreflang="fr" data-title="Matrice de permutation" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%B9%98%ED%99%98%ED%96%89%EB%A0%AC" title="치환행렬 – Korean" lang="ko" hreflang="ko" data-title="치환행렬" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Matriks_permutasi" title="Matriks permutasi – Indonesian" lang="id" hreflang="id" data-title="Matriks permutasi" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Matrice_di_permutazione" title="Matrice di permutazione – Italian" lang="it" hreflang="it" data-title="Matrice di permutazione" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%9E%D7%98%D7%A8%D7%99%D7%A6%D7%AA_%D7%AA%D7%9E%D7%95%D7%A8%D7%94" title="מטריצת תמורה – Hebrew" lang="he" hreflang="he" data-title="מטריצת תמורה" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Permut%C3%A1l%C3%B3_m%C3%A1trix" title="Permutáló mátrix – Hungarian" lang="hu" hreflang="hu" data-title="Permutáló mátrix" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Permutatiematrix" title="Permutatiematrix – Dutch" lang="nl" hreflang="nl" data-title="Permutatiematrix" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E7%BD%AE%E6%8F%9B%E8%A1%8C%E5%88%97" title="置換行列 – Japanese" lang="ja" hreflang="ja" data-title="置換行列" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pms mw-list-item"><a href="https://pms.wikipedia.org/wiki/Matris_%C3%ABd_p%C3%ABrmutassion" title="Matris ëd përmutassion – Piedmontese" lang="pms" hreflang="pms" data-title="Matris ëd përmutassion" data-language-autonym="Piemontèis" data-language-local-name="Piedmontese" class="interlanguage-link-target"><span>Piemontèis</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Matriz_de_permuta%C3%A7%C3%A3o" title="Matriz de permutação – Portuguese" lang="pt" hreflang="pt" data-title="Matriz de permutação" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Matrice_permutare" title="Matrice permutare – Romanian" lang="ro" hreflang="ro" data-title="Matrice permutare" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8" title="Матрица перестановки – Russian" lang="ru" hreflang="ru" data-title="Матрица перестановки" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Permutacijska_matrika" title="Permutacijska matrika – Slovenian" lang="sl" hreflang="sl" data-title="Permutacijska matrika" data-language-autonym="Slovenščina" data-language-local-name="Slovenian" class="interlanguage-link-target"><span>Slovenščina</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Permutaatiomatriisi" title="Permutaatiomatriisi – Finnish" lang="fi" hreflang="fi" data-title="Permutaatiomatriisi" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Permutationsmatris" title="Permutationsmatris – Swedish" lang="sv" hreflang="sv" data-title="Permutationsmatris" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-ta mw-list-item"><a href="https://ta.wikipedia.org/wiki/%E0%AE%B5%E0%AE%B0%E0%AE%BF%E0%AE%9A%E0%AF%88%E0%AE%AE%E0%AE%BE%E0%AE%B1%E0%AF%8D%E0%AE%B1_%E0%AE%85%E0%AE%A3%E0%AE%BF" title="வரிசைமாற்ற அணி – Tamil" lang="ta" hreflang="ta" data-title="வரிசைமாற்ற அணி" data-language-autonym="தமிழ்" data-language-local-name="Tamil" class="interlanguage-link-target"><span>தமிழ்</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8F_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8" title="Матриця перестановки – Ukrainian" lang="uk" hreflang="uk" data-title="Матриця перестановки" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Ma_tr%E1%BA%ADn_ho%C3%A1n_v%E1%BB%8B" title="Ma trận hoán vị – Vietnamese" lang="vi" hreflang="vi" data-title="Ma trận hoán vị" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E7%BD%AE%E6%8D%A2%E7%9F%A9%E9%98%B5" title="置换矩阵 – Chinese" lang="zh" hreflang="zh" data-title="置换矩阵" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q851512#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Permutation_matrix" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Permutation_matrix" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Permutation_matrix"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Permutation_matrix&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Permutation_matrix&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Permutation_matrix"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Permutation_matrix&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Permutation_matrix&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Permutation_matrix" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Permutation_matrix" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Permutation_matrix&oldid=1242522638" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Permutation_matrix&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Permutation_matrix&id=1242522638&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPermutation_matrix"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPermutation_matrix"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Permutation_matrix&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Permutation_matrix&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Permutation_matrices" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q851512" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Matrix with exactly one 1 per row and column</div> <p class="mw-empty-elt"> </p><p>In <a href="/wiki/Mathematics" title="Mathematics">mathematics</a>, particularly in <a href="/wiki/Matrix_(mathematics)" title="Matrix (mathematics)">matrix theory</a>, a <b>permutation matrix</b> is a square <a href="/wiki/Binary_matrix" class="mw-redirect" title="Binary matrix">binary matrix</a> that has exactly one entry of 1 in each row and each column with all other entries 0.<sup id="cite_ref-Artin_Algebra_1-0" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 26">: 26 </span></sup> An <span class="texhtml"><i>n</i> × <i>n</i></span> permutation matrix can represent a <a href="/wiki/Permutation" title="Permutation">permutation</a> of <span class="texhtml mvar" style="font-style:italic;">n</span> elements. Pre-<a href="/wiki/Matrix_multiplication" title="Matrix multiplication">multiplying</a> an <span class="texhtml mvar" style="font-style:italic;">n</span>-row matrix <span class="texhtml mvar" style="font-style:italic;">M</span> by a permutation matrix <span class="texhtml mvar" style="font-style:italic;">P</span>, forming <span class="texhtml mvar" style="font-style:italic;">PM</span>, results in permuting the rows of <span class="texhtml mvar" style="font-style:italic;">M</span>, while post-multiplying an <span class="texhtml mvar" style="font-style:italic;">n</span>-column matrix <span class="texhtml mvar" style="font-style:italic;">M</span>, forming <span class="texhtml mvar" style="font-style:italic;">MP</span>, permutes the columns of <span class="texhtml mvar" style="font-style:italic;">M</span>. </p><p>Every permutation matrix <i>P</i> is <a href="/wiki/Orthogonal_matrix" title="Orthogonal matrix">orthogonal</a>, with its <a href="/wiki/Invertible_matrix" title="Invertible matrix">inverse</a> equal to its <a href="/wiki/Transpose" title="Transpose">transpose</a>: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P^{-1}=P^{\mathsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>=</mo> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P^{-1}=P^{\mathsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/177fe3be7dbd0003f352837abb5d5b628bd71358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.426ex; height:2.676ex;" alt="{\displaystyle P^{-1}=P^{\mathsf {T}}}"></span>.<sup id="cite_ref-Artin_Algebra_1-1" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 26">: 26 </span></sup> Indeed, permutation matrices can be <a href="/wiki/Characterization_(mathematics)" title="Characterization (mathematics)">characterized</a> as the orthogonal matrices whose entries are all <a href="/wiki/Non-negative" class="mw-redirect" title="Non-negative">non-negative</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="The_two_permutation/matrix_correspondences"><span id="The_two_permutation.2Fmatrix_correspondences"></span>The two permutation/matrix correspondences</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=1" title="Edit section: The two permutation/matrix correspondences"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are two natural one-to-one correspondences between permutations and permutation matrices, one of which works along the rows of the matrix, the other along its columns. Here is an example, starting with a permutation <span class="texhtml mvar" style="font-style:italic;">π</span> in two-line form at the upper left: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{matrix}\pi \colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &R_{\pi }\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]C_{\pi }\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\pi ^{-1}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable rowspacing="0.9em 0.9em 0.4em" columnspacing="1em"> <mtr> <mtd> <mi>π</mi> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>2</mn> </mtd> <mtd> <mn>3</mn> </mtd> <mtd> <mn>4</mn> </mtd> </mtr> <mtr> <mtd> <mn>3</mn> </mtd> <mtd> <mn>2</mn> </mtd> <mtd> <mn>4</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> <mtd> <mo stretchy="false">⟷</mo> </mtd> <mtd> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo fence="true" symmetric="true" maxsize="1.623em" minsize="1.623em">↕</mo> </mrow> </mrow> </mtd> <mtd /> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo fence="true" symmetric="true" maxsize="1.623em" minsize="1.623em">↕</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> <mtd> <mo stretchy="false">⟷</mo> </mtd> <mtd> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>2</mn> </mtd> <mtd> <mn>3</mn> </mtd> <mtd> <mn>4</mn> </mtd> </mtr> <mtr> <mtd> <mn>4</mn> </mtd> <mtd> <mn>2</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>3</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\pi \colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &R_{\pi }\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]C_{\pi }\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\pi ^{-1}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/946618e2b33d2a42ee17069db241664df7bc4fcd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -15.671ex; width:50.512ex; height:32.509ex;" alt="{\displaystyle {\begin{matrix}\pi \colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &R_{\pi }\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]C_{\pi }\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\pi ^{-1}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}"></span></dd></dl> <p>The row-based correspondence takes the permutation <span class="texhtml mvar" style="font-style:italic;">π</span> to the matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f40348fb02b59e355aa3f191ce46a477f3b96293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.938ex; height:2.509ex;" alt="{\displaystyle R_{\pi }}"></span> at the upper right. The first row of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f40348fb02b59e355aa3f191ce46a477f3b96293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.938ex; height:2.509ex;" alt="{\displaystyle R_{\pi }}"></span> has its 1 in the third column because <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (1)=3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi (1)=3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e300002f803e8a18f2ed0cd920402f04763690b7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.565ex; height:2.843ex;" alt="{\displaystyle \pi (1)=3}"></span>. More generally, we have <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }=(r_{ij})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }=(r_{ij})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fa21a36ad452515217c1efe55946593b94fd0202" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.372ex; height:3.009ex;" alt="{\displaystyle R_{\pi }=(r_{ij})}"></span> where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{ij}=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{ij}=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1056123ee1c911186f66382327cbff0c819534f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.787ex; height:2.843ex;" alt="{\displaystyle r_{ij}=1}"></span> when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=\pi (i)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>=</mo> <mi>π</mi> <mo stretchy="false">(</mo> <mi>i</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j=\pi (i)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/89647e7e7b9c74a6cb282aae7cf2d9e0ef00a0ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:8.027ex; height:2.843ex;" alt="{\displaystyle j=\pi (i)}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{ij}=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{ij}=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/71aa662895ec402b922e2a7aebed82135ae42311" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.787ex; height:2.843ex;" alt="{\displaystyle r_{ij}=0}"></span> otherwise. </p><p>The column-based correspondence takes <span class="texhtml mvar" style="font-style:italic;">π</span> to the matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6df254544d63232d7da415655ccd4af50ea5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle C_{\pi }}"></span> at the lower left. The first column of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6df254544d63232d7da415655ccd4af50ea5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle C_{\pi }}"></span> has its 1 in the third row because <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (1)=3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi (1)=3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e300002f803e8a18f2ed0cd920402f04763690b7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.565ex; height:2.843ex;" alt="{\displaystyle \pi (1)=3}"></span>. More generally, we have <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }=(c_{ij})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }=(c_{ij})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c4b0dd300a88e442ba49cfec1e3e9539de3ee8e1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.228ex; height:3.009ex;" alt="{\displaystyle C_{\pi }=(c_{ij})}"></span> where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{ij}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c_{ij}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a106b8753c0948250bbc2e03df3207799beaedb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.484ex; height:2.343ex;" alt="{\displaystyle c_{ij}}"></span> is 1 when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=\pi (j)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>=</mo> <mi>π</mi> <mo stretchy="false">(</mo> <mi>j</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i=\pi (j)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3f41c6c2a6793a6e31f8a135e593c93abcc8f17d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8ex; height:2.843ex;" alt="{\displaystyle i=\pi (j)}"></span> and 0 otherwise. Since the two recipes differ only by swapping <i>i</i> with <i>j</i>, the matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6df254544d63232d7da415655ccd4af50ea5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle C_{\pi }}"></span> is the transpose of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f40348fb02b59e355aa3f191ce46a477f3b96293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.938ex; height:2.509ex;" alt="{\displaystyle R_{\pi }}"></span>; and, since <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f40348fb02b59e355aa3f191ce46a477f3b96293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.938ex; height:2.509ex;" alt="{\displaystyle R_{\pi }}"></span> is a permutation matrix, we have <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> <mo>=</mo> <msubsup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> </mrow> </mrow> </msubsup> <mo>=</mo> <msubsup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8102d8728475702f3830c69617efbd0955472a0f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.245ex; height:3.009ex;" alt="{\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}}"></span>. Tracing the other two sides of the big square, we have <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mrow> </msub> <mo>=</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> <mo>=</mo> <msubsup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8c8d62d3bd0261b3e6a23c74ccf802fc00a0c219" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.939ex; height:3.176ex;" alt="{\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi ^{-1}}=R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi ^{-1}}=R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7df3be38752effc2d69e2746a17bc5042f69b063" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.744ex; height:2.676ex;" alt="{\displaystyle C_{\pi ^{-1}}=R_{\pi }}"></span>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Permutation_matrices_permute_rows_or_columns">Permutation matrices permute rows or columns</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=2" title="Edit section: Permutation matrices permute rows or columns"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Multiplying a matrix <i>M</i> by either <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f40348fb02b59e355aa3f191ce46a477f3b96293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.938ex; height:2.509ex;" alt="{\displaystyle R_{\pi }}"></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6df254544d63232d7da415655ccd4af50ea5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle C_{\pi }}"></span> on either the left or the right will permute either the rows or columns of <i>M</i> by either <span class="texhtml mvar" style="font-style:italic;">π</span> or <span class="texhtml mvar" style="font-style:italic;">π</span><sup>−1</sup>. The details are a bit tricky. </p><p>To begin with, when we permute the entries of a vector <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (v_{1},\ldots ,v_{n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (v_{1},\ldots ,v_{n})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8ab0b34f196f25857f60aa90852f6ebba17a21ba" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.515ex; height:2.843ex;" alt="{\displaystyle (v_{1},\ldots ,v_{n})}"></span> by some permutation <span class="texhtml mvar" style="font-style:italic;">π</span>, we move the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{\text{th}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>i</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i^{\text{th}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/76cc827ec109594f9da6862138d76775cd733866" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.588ex; height:2.676ex;" alt="{\displaystyle i^{\text{th}}}"></span> entry <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}"></span> of the input vector into the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (i)^{\text{th}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> <mo stretchy="false">(</mo> <mi>i</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi (i)^{\text{th}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5c8eb3fac65e085f98bbf038fb649820a4b20256" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.73ex; height:3.176ex;" alt="{\displaystyle \pi (i)^{\text{th}}}"></span> slot of the output vector. Which entry then ends up in, say, the first slot of the output? Answer: The entry <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.037ex; height:2.343ex;" alt="{\displaystyle v_{j}}"></span> for which <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (j)=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> <mo stretchy="false">(</mo> <mi>j</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi (j)=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bf9356687be9d69c3e19560d7b2458967944f438" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.36ex; height:2.843ex;" alt="{\displaystyle \pi (j)=1}"></span>, and hence <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=\pi ^{-1}(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>=</mo> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j=\pi ^{-1}(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34b8ee02a8a31f4560da3421afc2158cba654d98" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:10.722ex; height:3.176ex;" alt="{\displaystyle j=\pi ^{-1}(1)}"></span>. Arguing similarly about each of the slots, we find that the output vector is </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\big (}v_{\pi ^{-1}(1)},v_{\pi ^{-1}(2)},\ldots ,v_{\pi ^{-1}(n)}{\big )},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> </mrow> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\big (}v_{\pi ^{-1}(1)},v_{\pi ^{-1}(2)},\ldots ,v_{\pi ^{-1}(n)}{\big )},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ecafdbdded0d46314d072adf23a38ce7e069623d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:27.976ex; height:3.343ex;" alt="{\displaystyle {\big (}v_{\pi ^{-1}(1)},v_{\pi ^{-1}(2)},\ldots ,v_{\pi ^{-1}(n)}{\big )},}"></span></dd></dl> <p>even though we are permuting by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9be4ba0bb8df3af72e90a0535fabcc17431e540a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }"></span>, not by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi ^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi ^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7a981d8eabb264a2b5c3b5f77c008f7b393eedb9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.667ex; height:2.676ex;" alt="{\displaystyle \pi ^{-1}}"></span>. Thus, in order to permute the entries by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9be4ba0bb8df3af72e90a0535fabcc17431e540a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }"></span>, we must permute the indices by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi ^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi ^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7a981d8eabb264a2b5c3b5f77c008f7b393eedb9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.667ex; height:2.676ex;" alt="{\displaystyle \pi ^{-1}}"></span>.<sup id="cite_ref-Artin_Algebra_1-2" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 25">: 25 </span></sup> (Permuting the entries by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9be4ba0bb8df3af72e90a0535fabcc17431e540a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }"></span> is sometimes called taking the <i>alibi viewpoint</i>, while permuting the indices by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9be4ba0bb8df3af72e90a0535fabcc17431e540a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }"></span> would take the <i>alias viewpoint</i>.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>) </p><p>Now, suppose that we pre-multiply some <i>n</i>-row matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M=(m_{i,j})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>,</mo> <mi>j</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M=(m_{i,j})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3f666385bf48e94c107bc0a56b0252eedf3848f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.325ex; height:3.009ex;" alt="{\displaystyle M=(m_{i,j})}"></span> by the permutation matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6df254544d63232d7da415655ccd4af50ea5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle C_{\pi }}"></span>. By the rule for <a href="/wiki/Matrix_multiplication" title="Matrix multiplication">matrix multiplication</a>, the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)^{\text{th}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>i</mi> <mo>,</mo> <mi>j</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (i,j)^{\text{th}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63722098b4be9e6fbc01cdb9154fa8a7171e8aa4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.39ex; height:3.176ex;" alt="{\displaystyle (i,j)^{\text{th}}}"></span> entry in the product <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }M}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> <mi>M</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }M}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9447f1ebb5cc76f25a52de9b16212ac84e57013f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.278ex; height:2.509ex;" alt="{\displaystyle C_{\pi }M}"></span> is </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{k=1}^{n}c_{i,k}m_{k,j},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> <msub> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>,</mo> <mi>j</mi> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \sum _{k=1}^{n}c_{i,k}m_{k,j},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dcf47176b775b3273ae6a13901fddc146dc01db8" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:11.773ex; height:6.843ex;" alt="{\displaystyle \sum _{k=1}^{n}c_{i,k}m_{k,j},}"></span></dd></dl> <p>where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i,k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c_{i,k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ff4f13e22868a578a5d63d62b675eabba562a567" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.12ex; height:2.343ex;" alt="{\displaystyle c_{i,k}}"></span> is 0 except when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=\pi (k)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>=</mo> <mi>π</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i=\pi (k)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/16c4ec7dbb56536a0d4fa8e541d3cbcd8ff3a823" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.253ex; height:2.843ex;" alt="{\displaystyle i=\pi (k)}"></span>, when it is 1. Thus, the only term in the sum that survives is the term in which <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=\pi ^{-1}(i)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>=</mo> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>i</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k=\pi ^{-1}(i)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a083cf86a0dc42c83295ca478bd5147685886df8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.588ex; height:3.176ex;" alt="{\displaystyle k=\pi ^{-1}(i)}"></span>, and the sum reduces to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{\pi ^{-1}(i),j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>i</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle m_{\pi ^{-1}(i),j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/736775b305a69f27cb6196964f4ef0375f725895" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:8.067ex; height:2.509ex;" alt="{\displaystyle m_{\pi ^{-1}(i),j}}"></span>. Since we have permuted the row index by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi ^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi ^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7a981d8eabb264a2b5c3b5f77c008f7b393eedb9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.667ex; height:2.676ex;" alt="{\displaystyle \pi ^{-1}}"></span>, we have permuted the rows of <i>M</i> themselves by <span class="texhtml mvar" style="font-style:italic;">π</span>.<sup id="cite_ref-Artin_Algebra_1-3" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 25">: 25 </span></sup> A similar argument shows that post-multiplying an <i>n</i>-column matrix <i>M</i> by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f40348fb02b59e355aa3f191ce46a477f3b96293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.938ex; height:2.509ex;" alt="{\displaystyle R_{\pi }}"></span> permutes its columns by <span class="texhtml mvar" style="font-style:italic;">π</span>. </p><p>The other two options are pre-multiplying by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f40348fb02b59e355aa3f191ce46a477f3b96293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.938ex; height:2.509ex;" alt="{\displaystyle R_{\pi }}"></span> or post-multiplying by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6df254544d63232d7da415655ccd4af50ea5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle C_{\pi }}"></span>, and they permute the rows or columns respectively by <span class="texhtml mvar" style="font-style:italic;">π</span><sup>−1</sup>, instead of by <span class="texhtml mvar" style="font-style:italic;">π</span>. </p> <div class="mw-heading mw-heading2"><h2 id="The_transpose_is_also_the_inverse">The transpose is also the inverse</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=3" title="Edit section: The transpose is also the inverse"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A related argument proves that, as we claimed above, the transpose of any permutation matrix <i>P</i> also acts as its inverse, which implies that <i>P</i> is invertible. (Artin leaves that proof as an exercise,<sup id="cite_ref-Artin_Algebra_1-4" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 26">: 26 </span></sup> which we here solve.) If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=(p_{i,j})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>,</mo> <mi>j</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P=(p_{i,j})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6310b3a1d7689608e57886c7123eb42b8ba358b2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.757ex; height:3.009ex;" alt="{\displaystyle P=(p_{i,j})}"></span>, then the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)^{\text{th}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>i</mi> <mo>,</mo> <mi>j</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (i,j)^{\text{th}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63722098b4be9e6fbc01cdb9154fa8a7171e8aa4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.39ex; height:3.176ex;" alt="{\displaystyle (i,j)^{\text{th}}}"></span> entry of its transpose <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P^{\mathsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P^{\mathsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1e1b184aec4e6472d6dfb82991a72e8e81a73e4f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.173ex; height:2.676ex;" alt="{\displaystyle P^{\mathsf {T}}}"></span> is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{j,i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>,</mo> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p_{j,i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bd09367f4b1c6b951d0d9916bc34b9153be29ea7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:3.193ex; height:2.343ex;" alt="{\displaystyle p_{j,i}}"></span>. The <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)^{\text{th}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>i</mi> <mo>,</mo> <mi>j</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (i,j)^{\text{th}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63722098b4be9e6fbc01cdb9154fa8a7171e8aa4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.39ex; height:3.176ex;" alt="{\displaystyle (i,j)^{\text{th}}}"></span> entry of the product <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle PP^{\mathsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle PP^{\mathsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d4f0f5957fa264793d21f0ffe2316d6668dd834" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.918ex; height:2.676ex;" alt="{\displaystyle PP^{\mathsf {T}}}"></span> is then </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{k=1}^{n}p_{i,k}p_{j,k}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \sum _{k=1}^{n}p_{i,k}p_{j,k}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4dcbda1144cbdfd7900539b57a69d9abb9041ad6" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:11.065ex; height:6.843ex;" alt="{\displaystyle \sum _{k=1}^{n}p_{i,k}p_{j,k}.}"></span></dd></dl> <p>Whenever <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\neq j}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>≠</mo> <mi>j</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i\neq j}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d95aeb406bb427ac96806bc00c30c91d31b858be" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.859ex; height:2.676ex;" alt="{\displaystyle i\neq j}"></span>, the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{\text{th}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k^{\text{th}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4972c293a203ef44247bcdc01bc77d6df0e21719" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.997ex; height:2.676ex;" alt="{\displaystyle k^{\text{th}}}"></span> term in this sum is the product of two different entries in the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{\text{th}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k^{\text{th}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4972c293a203ef44247bcdc01bc77d6df0e21719" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.997ex; height:2.676ex;" alt="{\displaystyle k^{\text{th}}}"></span> column of <i>P</i>; so all terms are 0, and the sum is 0. When <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=j}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>=</mo> <mi>j</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i=j}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/706e0928b2bf0f24076b0c90bb20616ff2068343" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.859ex; height:2.509ex;" alt="{\displaystyle i=j}"></span>, we are summing the squares of the entries in the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{\text{th}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>i</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i^{\text{th}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/76cc827ec109594f9da6862138d76775cd733866" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.588ex; height:2.676ex;" alt="{\displaystyle i^{\text{th}}}"></span> row of <i>P</i>, so the sum is 1. The product <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle PP^{\mathsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle PP^{\mathsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d4f0f5957fa264793d21f0ffe2316d6668dd834" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.918ex; height:2.676ex;" alt="{\displaystyle PP^{\mathsf {T}}}"></span> is thus the identity matrix. A symmetric argument shows the same for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P^{\mathsf {T}}P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> </mrow> </mrow> </msup> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P^{\mathsf {T}}P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3673931c93e27631f78294adcf4677f2f871ef59" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.918ex; height:2.676ex;" alt="{\displaystyle P^{\mathsf {T}}P}"></span>, implying that <i>P</i> is invertible with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P^{-1}=P^{\mathsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>=</mo> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P^{-1}=P^{\mathsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/177fe3be7dbd0003f352837abb5d5b628bd71358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.426ex; height:2.676ex;" alt="{\displaystyle P^{-1}=P^{\mathsf {T}}}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Multiplying_permutation_matrices">Multiplying permutation matrices</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=4" title="Edit section: Multiplying permutation matrices"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Given two permutations of <span class="texhtml"><i>n</i></span> elements 𝜎 and 𝜏, the product of the corresponding column-based permutation matrices <span class="texhtml"><i>C</i><sub>σ</sub></span> and <span class="texhtml"><i>C</i><sub>τ</sub></span> is given,<sup id="cite_ref-Artin_Algebra_1-5" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 25">: 25 </span></sup> as you might expect, by <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>σ</mi> </mrow> </msub> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>τ</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>σ</mi> <mspace width="thinmathspace" /> <mo>∘</mo> <mspace width="thinmathspace" /> <mi>τ</mi> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/04057b77bf4b2731a0440ab399777328b089f1c5" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.604ex; height:2.509ex;" alt="{\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },}"></span> where the composed permutation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma \circ \tau }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>σ</mi> <mo>∘</mo> <mi>τ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \sigma \circ \tau }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dbcb6cf1cbfe865863847d150775d690f7b68fb2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.726ex; height:1.676ex;" alt="{\displaystyle \sigma \circ \tau }"></span> applies first 𝜏 and then 𝜎, working from right to left: <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>σ</mi> <mo>∘</mo> <mi>τ</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>σ</mi> <mrow> <mo>(</mo> <mrow> <mi>τ</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo>)</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/79397575b11150ca067d9c93ca41d85456f7a180" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.437ex; height:2.843ex;" alt="{\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).}"></span> This follows because pre-multiplying some matrix by <span class="texhtml"><i>C</i><sub>τ</sub></span> and then pre-multiplying the resulting product by <span class="texhtml"><i>C</i><sub>σ</sub></span> gives the same result as pre-multiplying just once by the combined <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\sigma \,\circ \,\tau }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>σ</mi> <mspace width="thinmathspace" /> <mo>∘</mo> <mspace width="thinmathspace" /> <mi>τ</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\sigma \,\circ \,\tau }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bbbca096b87620489449d32bc68f7674b4c33a2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.28ex; height:2.509ex;" alt="{\displaystyle C_{\sigma \,\circ \,\tau }}"></span>. </p><p>For the row-based matrices, there is a twist: The product of <span class="texhtml"><i>R</i><sub>σ</sub></span> and <span class="texhtml"><i>R</i><sub>τ</sub></span> is given by </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\sigma }R_{\tau }=R_{\tau \,\circ \,\sigma },}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>σ</mi> </mrow> </msub> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>τ</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>τ</mi> <mspace width="thinmathspace" /> <mo>∘</mo> <mspace width="thinmathspace" /> <mi>σ</mi> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\sigma }R_{\tau }=R_{\tau \,\circ \,\sigma },}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/32964b10741646c5bdb6f2e6ea937eafae1aa8e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.911ex; height:2.509ex;" alt="{\displaystyle R_{\sigma }R_{\tau }=R_{\tau \,\circ \,\sigma },}"></span></dd></dl> <p>with 𝜎 applied before 𝜏 in the composed permutation. This happens because we must post-multiply to avoid inversions under the row-based option, so we would post-multiply first by <span class="texhtml"><i>R</i><sub>σ</sub></span> and then by <span class="texhtml"><i>R</i><sub>τ</sub></span>. </p><p>Some people, when applying a function to an argument, write the function after the argument (<a href="/wiki/Reverse_Polish_notation" title="Reverse Polish notation">postfix notation</a>), rather than before it. When doing linear algebra, they work with linear spaces of row vectors, and they apply a linear map to an argument by using the map's matrix to post-multiply the argument's row vector. They often use a left-to-right composition operator, which we here denote using a semicolon; so the composition <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma \,;\,\tau }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>σ</mi> <mspace width="thinmathspace" /> <mo>;</mo> <mspace width="thinmathspace" /> <mi>τ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \sigma \,;\,\tau }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cb7483420de71e508b40c4c12c500b38dbd84817" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.34ex; height:2.009ex;" alt="{\displaystyle \sigma \,;\,\tau }"></span> is defined either by </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\sigma \,;\,\tau )(k)=\tau \left(\sigma (k)\right),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>σ</mi> <mspace width="thinmathspace" /> <mo>;</mo> <mspace width="thinmathspace" /> <mi>τ</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>τ</mi> <mrow> <mo>(</mo> <mrow> <mi>σ</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo>)</mo> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\sigma \,;\,\tau )(k)=\tau \left(\sigma (k)\right),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0857a9c4f78b273d05e5ffeee17cc238ce6314b9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.051ex; height:2.843ex;" alt="{\displaystyle (\sigma \,;\,\tau )(k)=\tau \left(\sigma (k)\right),}"></span></dd></dl> <p>or, more elegantly, by </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (k)(\sigma \,;\,\tau )=\left((k)\sigma \right)\tau ,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mi>σ</mi> <mspace width="thinmathspace" /> <mo>;</mo> <mspace width="thinmathspace" /> <mi>τ</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mi>σ</mi> </mrow> <mo>)</mo> </mrow> <mi>τ</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (k)(\sigma \,;\,\tau )=\left((k)\sigma \right)\tau ,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7415013a28e61173b545afaa8e34ad90a0fe323b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.663ex; height:2.843ex;" alt="{\displaystyle (k)(\sigma \,;\,\tau )=\left((k)\sigma \right)\tau ,}"></span></dd></dl> <p>with 𝜎 applied first. That notation gives us a simpler rule for multiplying row-based permutation matrices: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\sigma }R_{\tau }=R_{\sigma \,;\,\tau }.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>σ</mi> </mrow> </msub> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>τ</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>σ</mi> <mspace width="thinmathspace" /> <mo>;</mo> <mspace width="thinmathspace" /> <mi>τ</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\sigma }R_{\tau }=R_{\sigma \,;\,\tau }.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5c3f13a833cd2c19ce98a39283ab3e203345bccb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.546ex; height:2.843ex;" alt="{\displaystyle R_{\sigma }R_{\tau }=R_{\sigma \,;\,\tau }.}"></span></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Matrix_group">Matrix group</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=5" title="Edit section: Matrix group"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>When <span class="texhtml mvar" style="font-style:italic;">π</span> is the identity permutation, which has <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi (i)=i}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>π</mi> <mo stretchy="false">(</mo> <mi>i</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>i</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \pi (i)=i}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/35fdd04f3e728e9bb3cc0e8cf1c6539e44ed77b6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.845ex; height:2.843ex;" alt="{\displaystyle \pi (i)=i}"></span> for all <i>i</i>, both <span class="texhtml"><i>C</i><sub><span class="texhtml mvar" style="font-style:italic;">π</span></sub></span> and <span class="texhtml"><i>R</i><sub><span class="texhtml mvar" style="font-style:italic;">π</span></sub></span> are the <a href="/wiki/Identity_matrix" title="Identity matrix">identity matrix</a>. </p><p>There are <span class="texhtml"><i>n</i>!</span> permutation matrices, since there are <span class="texhtml"><i>n</i>!</span> permutations and the map <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\colon \pi \mapsto C_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo>:</mo> <mi>π</mi> <mo stretchy="false">↦</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C\colon \pi \mapsto C_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ad11b92f3d3bb9eda9a75569d9f5281c7db9d6e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.582ex; height:2.509ex;" alt="{\displaystyle C\colon \pi \mapsto C_{\pi }}"></span> is a one-to-one correspondence between permutations and permutation matrices. (The map <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></span> is another such correspondence.) By the formulas above, those <span class="texhtml"><i>n</i> × <i>n</i></span> permutation matrices form a <a href="/wiki/Group_(mathematics)" title="Group (mathematics)">group</a> of order <span class="texhtml"><i>n</i>!</span> under matrix multiplication, with the identity matrix as its <a href="/wiki/Identity_element" title="Identity element">identity element</a>, a group that we denote <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18b28e0cb7064400f07370c0d35d46b6875e17e1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle {\mathcal {P}}_{n}}"></span>. The group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18b28e0cb7064400f07370c0d35d46b6875e17e1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle {\mathcal {P}}_{n}}"></span> is a subgroup of the <a href="/wiki/General_linear_group" title="General linear group">general linear group</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle GL_{n}(\mathbb {R} )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle GL_{n}(\mathbb {R} )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/769b4aad19f5b8ba0dd097a533893d83d1534e7b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.115ex; height:2.843ex;" alt="{\displaystyle GL_{n}(\mathbb {R} )}"></span> of invertible <span class="texhtml"><i>n</i> × <i>n</i></span> matrices of real numbers. Indeed, for any <a href="/wiki/Field_(mathematics)" title="Field (mathematics)">field</a> <i>F</i>, the group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18b28e0cb7064400f07370c0d35d46b6875e17e1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle {\mathcal {P}}_{n}}"></span> is also a subgroup of the group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle GL_{n}(F)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>F</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle GL_{n}(F)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/37e5855f2ae418faadee665f13b008f04db64183" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.178ex; height:2.843ex;" alt="{\displaystyle GL_{n}(F)}"></span>, where the matrix entries belong to <i>F</i>. (Every field contains 0 and 1 with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0+0=0,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> <mo>+</mo> <mn>0</mn> <mo>=</mo> <mn>0</mn> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0+0=0,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d3a5668c61699c8a32c66bc8ca210d8522443be0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.073ex; height:2.509ex;" alt="{\displaystyle 0+0=0,}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0+1=1,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> <mo>+</mo> <mn>1</mn> <mo>=</mo> <mn>1</mn> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0+1=1,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2aff6d4c6a5132755ded1075221d2140c4873dc7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.073ex; height:2.509ex;" alt="{\displaystyle 0+1=1,}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0*0=0,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> <mo>∗</mo> <mn>0</mn> <mo>=</mo> <mn>0</mn> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0*0=0,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c4fe4c19bb117b372c9429ec1d289346f892b4f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.427ex; height:2.509ex;" alt="{\displaystyle 0*0=0,}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0*1=0,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> <mo>∗</mo> <mn>1</mn> <mo>=</mo> <mn>0</mn> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0*1=0,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57fb91e14d6197235d9391e939b5da153819aa51" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.427ex; height:2.509ex;" alt="{\displaystyle 0*1=0,}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1*1=1;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>∗</mo> <mn>1</mn> <mo>=</mo> <mn>1</mn> <mo>;</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1*1=1;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e9ca7e3e2f93d9f0c7ab0b751ec10a1e9f24bf2e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.427ex; height:2.509ex;" alt="{\displaystyle 1*1=1;}"></span> and that's all we need to multiply permutation matrices. Different fields disagree about whether <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+1=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>+</mo> <mn>1</mn> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1+1=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8a94a15bb0333c813ac2ed0d697e5e57092cbbc8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.426ex; height:2.343ex;" alt="{\displaystyle 1+1=0}"></span>, but that sum doesn't arise.) </p><p>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{n}^{\leftarrow }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">←</mo> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{n}^{\leftarrow }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9186f3c94f04701aa94004b9ce9de3dda6e9d0cf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.397ex; height:2.509ex;" alt="{\displaystyle S_{n}^{\leftarrow }}"></span> denote the <a href="/wiki/Symmetric_group" title="Symmetric group">symmetric group</a>, or <a href="/wiki/Permutation_group" title="Permutation group">group of permutations</a>, on {1,2,...,<span class="texhtml"><i>n</i></span>} where the group operation is the standard, right-to-left composition "<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \circ }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>∘</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \circ }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/99add39d2b681e2de7ff62422c32704a05c7ec31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.125ex; margin-bottom: -0.297ex; width:1.162ex; height:1.509ex;" alt="{\displaystyle \circ }"></span>"; and let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{n}^{\rightarrow }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">→</mo> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{n}^{\rightarrow }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19449cceba4cff777addeac3c88232bfeae911a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.397ex; height:2.509ex;" alt="{\displaystyle S_{n}^{\rightarrow }}"></span> denote the <a href="/wiki/Opposite_group" title="Opposite group">opposite group</a>, which uses the left-to-right composition "<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,;\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thinmathspace" /> <mo>;</mo> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \,;\,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/208135e9acdccdbd07b068e22ec5b1ba679157a3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.421ex; height:2.009ex;" alt="{\displaystyle \,;\,}"></span>". The map <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\colon S_{n}^{\leftarrow }\to GL_{n}(\mathbb {R} )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo>:</mo> <msubsup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">←</mo> </mrow> </msubsup> <mo stretchy="false">→</mo> <mi>G</mi> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C\colon S_{n}^{\leftarrow }\to GL_{n}(\mathbb {R} )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a17a564c98ab36c975ee580e2db1969495317f83" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.927ex; height:2.843ex;" alt="{\displaystyle C\colon S_{n}^{\leftarrow }\to GL_{n}(\mathbb {R} )}"></span> that takes <span class="texhtml mvar" style="font-style:italic;">π</span> to its column-based matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6df254544d63232d7da415655ccd4af50ea5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.836ex; height:2.509ex;" alt="{\displaystyle C_{\pi }}"></span> is a <a href="/wiki/Faithful_representation" title="Faithful representation">faithful representation</a>, and similarly for the map <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\colon S_{n}^{\rightarrow }\to GL_{n}(\mathbb {R} )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>:</mo> <msubsup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">→</mo> </mrow> </msubsup> <mo stretchy="false">→</mo> <mi>G</mi> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\colon S_{n}^{\rightarrow }\to GL_{n}(\mathbb {R} )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8f627567762ce3706b3dcdafc79dc1a34beddeb2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.924ex; height:2.843ex;" alt="{\displaystyle R\colon S_{n}^{\rightarrow }\to GL_{n}(\mathbb {R} )}"></span> that takes <span class="texhtml mvar" style="font-style:italic;">π</span> to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\pi }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>π</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\pi }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f40348fb02b59e355aa3f191ce46a477f3b96293" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.938ex; height:2.509ex;" alt="{\displaystyle R_{\pi }}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Doubly_stochastic_matrices">Doubly stochastic matrices</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=6" title="Edit section: Doubly stochastic matrices"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Every permutation matrix is <a href="/wiki/Doubly_stochastic_matrix" title="Doubly stochastic matrix">doubly stochastic</a>. The set of all doubly stochastic matrices is called the <a href="/wiki/Birkhoff_polytope" title="Birkhoff polytope">Birkhoff polytope</a>, and the permutation matrices play a special role in that polytope. The <a href="/wiki/Birkhoff%E2%80%93von_Neumann_theorem" class="mw-redirect" title="Birkhoff–von Neumann theorem">Birkhoff–von Neumann theorem</a> says that every doubly stochastic real matrix is a <a href="/wiki/Convex_combination" title="Convex combination">convex combination</a> of permutation matrices of the same order, with the permutation matrices being precisely the <a href="/wiki/Extreme_point" title="Extreme point">extreme points</a> (the vertices) of the Birkhoff polytope. The Birkhoff polytope is thus the <a href="/wiki/Convex_hull" title="Convex hull">convex hull</a> of the permutation matrices.<sup id="cite_ref-Bru19_5-0" class="reference"><a href="#cite_note-Bru19-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Linear-algebraic_properties">Linear-algebraic properties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=7" title="Edit section: Linear-algebraic properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Just as each permutation is associated with two permutation matrices, each permutation matrix is associated with two permutations, as we can see by relabeling the example in the big square above starting with the matrix <i>P</i> at the upper right: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{matrix}\rho _{P}\colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &P\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]P^{-1}\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\kappa _{P}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable rowspacing="0.9em 0.9em 0.4em" columnspacing="1em"> <mtr> <mtd> <msub> <mi>ρ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>2</mn> </mtd> <mtd> <mn>3</mn> </mtd> <mtd> <mn>4</mn> </mtd> </mtr> <mtr> <mtd> <mn>3</mn> </mtd> <mtd> <mn>2</mn> </mtd> <mtd> <mn>4</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> <mtd> <mo stretchy="false">⟷</mo> </mtd> <mtd> <mi>P</mi> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo fence="true" symmetric="true" maxsize="1.623em" minsize="1.623em">↕</mo> </mrow> </mrow> </mtd> <mtd /> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo fence="true" symmetric="true" maxsize="1.623em" minsize="1.623em">↕</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> <mtd> <mo stretchy="false">⟷</mo> </mtd> <mtd> <msub> <mi>κ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>2</mn> </mtd> <mtd> <mn>3</mn> </mtd> <mtd> <mn>4</mn> </mtd> </mtr> <mtr> <mtd> <mn>4</mn> </mtd> <mtd> <mn>2</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>3</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\rho _{P}\colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &P\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]P^{-1}\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\kappa _{P}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e8a4c616677a8119ee12b531ab7a5cb284f8224" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -15.671ex; width:50.969ex; height:32.509ex;" alt="{\displaystyle {\begin{matrix}\rho _{P}\colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &P\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]P^{-1}\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\kappa _{P}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}"></span></dd></dl> <p>So we are here denoting the inverse of <i>C</i> as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \kappa }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>κ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \kappa }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/54ddec2e922c5caea4e47d04feef86e782dc8e6d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:1.676ex;" alt="{\displaystyle \kappa }"></span> and the inverse of <i>R</i> as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ρ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rho }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f7d439671d1289b6a816e6af7a304be40608d64" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }"></span>. We can then compute the linear-algebraic properties of <i>P</i> from some combinatorial properties that are shared by the two permutations <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \kappa _{P}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>κ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \kappa _{P}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2235078248c2bf36318d7114e69fe3591cb86c31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.805ex; height:2.009ex;" alt="{\displaystyle \kappa _{P}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho _{P}=\kappa _{P}^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ρ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> <mo>=</mo> <msubsup> <mi>κ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rho _{P}=\kappa _{P}^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/13a400965f31022047943af4f0cfa913c145ba31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.439ex; height:3.343ex;" alt="{\displaystyle \rho _{P}=\kappa _{P}^{-1}}"></span>. </p><p>A point is <a href="/wiki/Fixed_point_(mathematics)" title="Fixed point (mathematics)">fixed</a> by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \kappa _{P}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>κ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \kappa _{P}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2235078248c2bf36318d7114e69fe3591cb86c31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.805ex; height:2.009ex;" alt="{\displaystyle \kappa _{P}}"></span> just when it is fixed by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho _{P}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ρ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rho _{P}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/622c26d6f6f10905ad0b3d1d35027bdc024c9d73" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.668ex; height:2.176ex;" alt="{\displaystyle \rho _{P}}"></span>, and the <a href="/wiki/Trace_(linear_algebra)" title="Trace (linear algebra)">trace</a> of <i>P</i> is the number of such shared fixed points.<sup id="cite_ref-Artin_Algebra_1-6" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 322">: 322 </span></sup> If the integer <i>k</i> is one of them, then the <a href="/wiki/Standard_basis" title="Standard basis">standard basis</a> vector <span class="texhtml"><i><b>e</b></i><sub><i>k</i></sub></span> is an <a href="/wiki/Eigenvector" class="mw-redirect" title="Eigenvector">eigenvector</a> of <i>P</i>.<sup id="cite_ref-Artin_Algebra_1-7" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 118">: 118 </span></sup> </p><p>To calculate the complex <a href="/wiki/Eigenvalue" class="mw-redirect" title="Eigenvalue">eigenvalues</a> of <i>P</i>, write the permutation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \kappa _{P}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>κ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \kappa _{P}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2235078248c2bf36318d7114e69fe3591cb86c31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.805ex; height:2.009ex;" alt="{\displaystyle \kappa _{P}}"></span> as a composition of <a href="/wiki/Cyclic_permutation" title="Cyclic permutation">disjoint cycles</a>, say <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \kappa _{P}=c_{1}c_{2}\cdots c_{t}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>κ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⋯</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \kappa _{P}=c_{1}c_{2}\cdots c_{t}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ac268de9ee21af4946601e66b8de0b4ee1918926" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.356ex; height:2.009ex;" alt="{\displaystyle \kappa _{P}=c_{1}c_{2}\cdots c_{t}}"></span>. (Permutations of disjoint subsets commute, so it doesn't matter here whether we are composing right-to-left or left-to-right.) For <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq t}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo>≤</mo> <mi>t</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq t}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/17c608ea4232d96835475fc9ec0aafe6e9a611a7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.001ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq t}"></span>, let the length of the cycle <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01acb7953ba52c2aa44264b5d0f8fd223aa178a2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.807ex; height:2.009ex;" alt="{\displaystyle c_{i}}"></span> be <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ℓ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \ell _{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc03cf8f5f3927c6693a9ac9677685b08b29c106" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.769ex; height:2.509ex;" alt="{\displaystyle \ell _{i}}"></span>, and let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fbbedf9f5f71ca52f8f24392c3cc18fca6c420dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.383ex; height:2.509ex;" alt="{\displaystyle L_{i}}"></span> be the set of complex solutions of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{\ell _{i}}=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>ℓ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mrow> </msup> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{\ell _{i}}=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/789e538b51459419300790c5cd85495f6a92b3f6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.133ex; height:2.676ex;" alt="{\displaystyle x^{\ell _{i}}=1}"></span>, those solutions being the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{i}^{\,{\text{th}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>ℓ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mspace width="thinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mtext>th</mtext> </mrow> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \ell _{i}^{\,{\text{th}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/96c21f8b7e734ee2f714dc63ffa7286b2ba6cda7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.143ex; height:3.176ex;" alt="{\displaystyle \ell _{i}^{\,{\text{th}}}}"></span> <a href="/wiki/Root_of_unity" title="Root of unity">roots of unity</a>. The <a href="/wiki/Multiset" title="Multiset">multiset</a> union of the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fbbedf9f5f71ca52f8f24392c3cc18fca6c420dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.383ex; height:2.509ex;" alt="{\displaystyle L_{i}}"></span> is then the multiset of eigenvalues of <i>P</i>. Since writing <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho _{P}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ρ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rho _{P}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/622c26d6f6f10905ad0b3d1d35027bdc024c9d73" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.668ex; height:2.176ex;" alt="{\displaystyle \rho _{P}}"></span> as a product of cycles would give the same number of cycles of the same lengths, analyzing <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho _{p}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ρ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rho _{p}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e49d430cea45dcf636733f321ecc108b41c1836c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.261ex; height:2.343ex;" alt="{\displaystyle \rho _{p}}"></span> would give the same result. The <a href="/wiki/Eigenvalues_and_eigenvectors#Eigenvalues_and_eigenvectors_of_matrices" title="Eigenvalues and eigenvectors">multiplicity</a> of any eigenvalue <i>v</i> is the number of <i>i</i> for which <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fbbedf9f5f71ca52f8f24392c3cc18fca6c420dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.383ex; height:2.509ex;" alt="{\displaystyle L_{i}}"></span> contains <i>v</i>.<sup id="cite_ref-J_Najnudel2010_4_6-0" class="reference"><a href="#cite_note-J_Najnudel2010_4-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> (Since any permutation matrix is <a href="/wiki/Normal_matrices" class="mw-redirect" title="Normal matrices">normal</a> and any normal matrix is <a href="/wiki/Diagonalizable_matrix" title="Diagonalizable matrix">diagonalizable</a> over the complex numbers,<sup id="cite_ref-Artin_Algebra_1-8" class="reference"><a href="#cite_note-Artin_Algebra-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 259">: 259 </span></sup> the algebraic and geometric multiplicities of an eigenvalue <i>v</i> are the same.) </p><p>From <a href="/wiki/Group_theory" title="Group theory">group theory</a> we know that any permutation may be written as a composition of <a href="/wiki/Transposition_(mathematics)" class="mw-redirect" title="Transposition (mathematics)">transpositions</a>. Therefore, any permutation matrix factors as a product of row-switching <a href="/wiki/Elementary_matrix" title="Elementary matrix">elementary matrices</a>, each of which has <a href="/wiki/Determinant" title="Determinant">determinant</a> −1. Thus, the determinant of the permutation matrix <i>P</i> is the <a href="/wiki/Parity_of_a_permutation" title="Parity of a permutation">sign</a> of the permutation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \kappa _{P}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>κ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \kappa _{P}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2235078248c2bf36318d7114e69fe3591cb86c31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.805ex; height:2.009ex;" alt="{\displaystyle \kappa _{P}}"></span>, which is also the sign of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho _{P}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ρ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rho _{P}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/622c26d6f6f10905ad0b3d1d35027bdc024c9d73" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.668ex; height:2.176ex;" alt="{\displaystyle \rho _{P}}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Restricted_forms">Restricted forms</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=8" title="Edit section: Restricted forms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Costas_array" title="Costas array">Costas array</a>, a permutation matrix in which the displacement vectors between the entries are all distinct</li> <li><a href="/wiki/Eight_queens_puzzle" title="Eight queens puzzle">n-queens puzzle</a>, a permutation matrix in which there is at most one entry in each diagonal and antidiagonal</li></ul> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=9" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Alternating_sign_matrix" title="Alternating sign matrix">Alternating sign matrix</a></li> <li><a href="/wiki/Exchange_matrix" title="Exchange matrix">Exchange matrix</a></li> <li><a href="/wiki/Generalized_permutation_matrix" title="Generalized permutation matrix">Generalized permutation matrix</a></li> <li><a href="/wiki/Rook_polynomial" title="Rook polynomial">Rook polynomial</a></li> <li><a href="/wiki/Permanent_(mathematics)" title="Permanent (mathematics)">Permanent</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Permutation_matrix&action=edit&section=10" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-Artin_Algebra-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-Artin_Algebra_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Artin_Algebra_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Artin_Algebra_1-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-Artin_Algebra_1-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-Artin_Algebra_1-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-Artin_Algebra_1-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-Artin_Algebra_1-6"><sup><i><b>g</b></i></sup></a> <a href="#cite_ref-Artin_Algebra_1-7"><sup><i><b>h</b></i></sup></a> <a href="#cite_ref-Artin_Algebra_1-8"><sup><i><b>i</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFArtin1991" class="citation book cs1"><a href="/wiki/Michael_Artin" title="Michael Artin">Artin, Michael</a> (1991). <i>Algebra</i>. Prentice Hall. pp. 24–26, 118, 259, 322. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-13-004763-5" title="Special:BookSources/0-13-004763-5"><bdi>0-13-004763-5</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/24364036">24364036</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algebra&rft.pages=24-26%2C+118%2C+259%2C+322&rft.pub=Prentice+Hall&rft.date=1991&rft_id=info%3Aoclcnum%2F24364036&rft.isbn=0-13-004763-5&rft.aulast=Artin&rft.aufirst=Michael&rfr_id=info%3Asid%2Fen.wikipedia.org%3APermutation+matrix" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFZavlanosPappas2008" class="citation journal cs1">Zavlanos, Michael M.; Pappas, George J. (November 2008). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/abs/pii/S0005109808002616">"A dynamical systems approach to weighted graph matching"</a>. <i>Automatica</i>. <b>44</b> (11): 2817–2824. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.128.6870">10.1.1.128.6870</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.automatica.2008.04.009">10.1016/j.automatica.2008.04.009</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:834305">834305</a><span class="reference-accessdate">. Retrieved <span class="nowrap">21 August</span> 2022</span>. <q>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>O</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4430e805a5f519b46eea4ec0d2dc04fc2fd19028" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.992ex; height:2.509ex;" alt="{\displaystyle O_{n}}"></span> denote the set of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>×</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59d2b4cb72e304526cf5b5887147729ea259da78" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}"></span> orthogonal matrices and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e1726319d75a0531be1b14f4f9a0c3bee00b786a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.085ex; height:2.509ex;" alt="{\displaystyle N_{n}}"></span> denote the set of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>×</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59d2b4cb72e304526cf5b5887147729ea259da78" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}"></span> element-wise non-negative matrices. Then, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{n}=O_{n}\cap N_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>O</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>∩</mo> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{n}=O_{n}\cap N_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f4a6bdcfaa489f8a74a1480e8b9a37212552728d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.468ex; height:2.509ex;" alt="{\displaystyle P_{n}=O_{n}\cap N_{n}}"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5949c8b1de44005a1af3a11188361f2a830842d1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.711ex; height:2.509ex;" alt="{\displaystyle P_{n}}"></span> is the set of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>×</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59d2b4cb72e304526cf5b5887147729ea259da78" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}"></span> permutation matrices.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Automatica&rft.atitle=A+dynamical+systems+approach+to+weighted+graph+matching&rft.volume=44&rft.issue=11&rft.pages=2817-2824&rft.date=2008-11&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.128.6870%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A834305%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1016%2Fj.automatica.2008.04.009&rft.aulast=Zavlanos&rft.aufirst=Michael+M.&rft.au=Pappas%2C+George+J.&rft_id=https%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fabs%2Fpii%2FS0005109808002616&rfr_id=info%3Asid%2Fen.wikipedia.org%3APermutation+matrix" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">This terminology is not standard. Most authors use just one of the two correspondences, choosing which to be consistent with their other conventions. For example, Artin uses the column-based correspondence. We have here invented two names in order to discuss both options.</span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFConwayBurgielGoodman-Strauss2008" class="citation book cs1"><a href="/wiki/John_H._Conway" class="mw-redirect" title="John H. Conway">Conway, John H.</a>; Burgiel, Heidi; <a href="/wiki/Chaim_Goodman-Strauss" title="Chaim Goodman-Strauss">Goodman-Strauss, Chaim</a> (2008). <i>The Symmetries of Things</i>. A K Peters/CRC Press. p. 179. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1201%2Fb21368">10.1201/b21368</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-429-06306-0" title="Special:BookSources/978-0-429-06306-0"><bdi>978-0-429-06306-0</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/946786108">946786108</a>. <q>A permutation—say, of the names of a number of people—can be thought of as moving either the names or the people. The alias viewpoint regards the permutation as assigning a new name or <i>alias</i> to each person (from the Latin <i>alias</i> = otherwise). Alternatively, from the alibi viewoint we move the people to the places corresponding to their new names (from the Latin <i>alibi</i> = in another place.)</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Symmetries+of+Things&rft.pages=179&rft.pub=A+K+Peters%2FCRC+Press&rft.date=2008&rft_id=info%3Aoclcnum%2F946786108&rft_id=info%3Adoi%2F10.1201%2Fb21368&rft.isbn=978-0-429-06306-0&rft.aulast=Conway&rft.aufirst=John+H.&rft.au=Burgiel%2C+Heidi&rft.au=Goodman-Strauss%2C+Chaim&rfr_id=info%3Asid%2Fen.wikipedia.org%3APermutation+matrix" class="Z3988"></span></span> </li> <li id="cite_note-Bru19-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Bru19_5-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFBrualdi2006">Brualdi 2006</a>, p. 19</span> </li> <li id="cite_note-J_Najnudel2010_4-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-J_Najnudel2010_4_6-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFNajnudelNikeghbali2013">Najnudel & Nikeghbali 2013</a>, p. 4</span> </li> </ol></div></div> <style data-mw-deduplicate="TemplateStyles:r1239549316">.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}</style><div class="refbegin" style=""> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrualdi2006" class="citation book cs1">Brualdi, Richard A. (2006). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/combinatorialmat0000brua"><i>Combinatorial matrix classes</i></a></span>. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-86565-4" title="Special:BookSources/0-521-86565-4"><bdi>0-521-86565-4</bdi></a>. <a href="/wiki/Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1106.05001">1106.05001</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Combinatorial+matrix+classes&rft.place=Cambridge&rft.series=Encyclopedia+of+Mathematics+and+Its+Applications&rft.pub=Cambridge+University+Press&rft.date=2006&rft_id=https%3A%2F%2Fzbmath.org%2F%3Fformat%3Dcomplete%26q%3Dan%3A1106.05001%23id-name%3DZbl&rft.isbn=0-521-86565-4&rft.aulast=Brualdi&rft.aufirst=Richard+A.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcombinatorialmat0000brua&rfr_id=info%3Asid%2Fen.wikipedia.org%3APermutation+matrix" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFNajnudelNikeghbali2013" class="citation cs2">Najnudel, Joseph; <a href="/wiki/Ashkan_Nikeghbali" title="Ashkan Nikeghbali">Nikeghbali, Ashkan</a> (2013) [2010], <a rel="nofollow" class="external text" href="http://www.numdam.org/item/AIF_2013__63_3_773_0/">"The Distribution of Eigenvalues of Randomized Permutation Matrices"</a>, <i>Annales de l'Institut Fourier</i>, <b>63</b> (3): 773–838, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1005.0402">1005.0402</a></span>, <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2010arXiv1005.0402N">2010arXiv1005.0402N</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annales+de+l%27Institut+Fourier&rft.atitle=The+Distribution+of+Eigenvalues+of+Randomized+Permutation+Matrices&rft.volume=63&rft.issue=3&rft.pages=773-838&rft.date=2013&rft_id=info%3Aarxiv%2F1005.0402&rft_id=info%3Abibcode%2F2010arXiv1005.0402N&rft.aulast=Najnudel&rft.aufirst=Joseph&rft.au=Nikeghbali%2C+Ashkan&rft_id=http%3A%2F%2Fwww.numdam.org%2Fitem%2FAIF_2013__63_3_773_0%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3APermutation+matrix" class="Z3988"></span></li></ul> </div> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Matrix_classes" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Matrix_classes" title="Template:Matrix classes"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Matrix_classes" title="Template talk:Matrix classes"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Matrix_classes" title="Special:EditPage/Template:Matrix classes"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Matrix_classes" style="font-size:114%;margin:0 4em"><a href="/wiki/Matrix_(mathematics)" title="Matrix (mathematics)">Matrix</a> classes</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Explicitly constrained entries</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Alternant_matrix" title="Alternant matrix">Alternant</a></li> <li><a href="/wiki/Anti-diagonal_matrix" title="Anti-diagonal matrix">Anti-diagonal</a></li> <li><a href="/wiki/Skew-Hermitian_matrix" title="Skew-Hermitian matrix">Anti-Hermitian</a></li> <li><a href="/wiki/Skew-symmetric_matrix" title="Skew-symmetric matrix">Anti-symmetric</a></li> <li><a href="/wiki/Arrowhead_matrix" title="Arrowhead matrix">Arrowhead</a></li> <li><a href="/wiki/Band_matrix" title="Band matrix">Band</a></li> <li><a href="/wiki/Bidiagonal_matrix" title="Bidiagonal matrix">Bidiagonal</a></li> <li><a href="/wiki/Bisymmetric_matrix" title="Bisymmetric matrix">Bisymmetric</a></li> <li><a href="/wiki/Block-diagonal_matrix" class="mw-redirect" title="Block-diagonal matrix">Block-diagonal</a></li> <li><a href="/wiki/Block_matrix" title="Block matrix">Block</a></li> <li><a href="/wiki/Block_tridiagonal_matrix" class="mw-redirect" title="Block tridiagonal matrix">Block tridiagonal</a></li> <li><a href="/wiki/Boolean_matrix" title="Boolean matrix">Boolean</a></li> <li><a href="/wiki/Cauchy_matrix" title="Cauchy matrix">Cauchy</a></li> <li><a href="/wiki/Centrosymmetric_matrix" title="Centrosymmetric matrix">Centrosymmetric</a></li> <li><a href="/wiki/Conference_matrix" title="Conference matrix">Conference</a></li> <li><a href="/wiki/Complex_Hadamard_matrix" title="Complex Hadamard matrix">Complex Hadamard</a></li> <li><a href="/wiki/Copositive_matrix" title="Copositive matrix">Copositive</a></li> <li><a href="/wiki/Diagonally_dominant_matrix" title="Diagonally dominant matrix">Diagonally dominant</a></li> <li><a href="/wiki/Diagonal_matrix" title="Diagonal matrix">Diagonal</a></li> <li><a href="/wiki/DFT_matrix" title="DFT matrix">Discrete Fourier Transform</a></li> <li><a href="/wiki/Elementary_matrix" title="Elementary matrix">Elementary</a></li> <li><a href="/wiki/Equivalent_matrix" class="mw-redirect" title="Equivalent matrix">Equivalent</a></li> <li><a href="/wiki/Frobenius_matrix" title="Frobenius matrix">Frobenius</a></li> <li><a href="/wiki/Generalized_permutation_matrix" title="Generalized permutation matrix">Generalized permutation</a></li> <li><a href="/wiki/Hadamard_matrix" title="Hadamard matrix">Hadamard</a></li> <li><a href="/wiki/Hankel_matrix" title="Hankel matrix">Hankel</a></li> <li><a href="/wiki/Hermitian_matrix" title="Hermitian matrix">Hermitian</a></li> <li><a href="/wiki/Hessenberg_matrix" title="Hessenberg matrix">Hessenberg</a></li> <li><a href="/wiki/Hollow_matrix" title="Hollow matrix">Hollow</a></li> <li><a href="/wiki/Integer_matrix" title="Integer matrix">Integer</a></li> <li><a href="/wiki/Logical_matrix" title="Logical matrix">Logical</a></li> <li><a href="/wiki/Matrix_unit" title="Matrix unit">Matrix unit</a></li> <li><a href="/wiki/Metzler_matrix" title="Metzler matrix">Metzler</a></li> <li><a href="/wiki/Moore_matrix" title="Moore matrix">Moore</a></li> <li><a href="/wiki/Nonnegative_matrix" title="Nonnegative matrix">Nonnegative</a></li> <li><a href="/wiki/Pentadiagonal_matrix" class="mw-redirect" title="Pentadiagonal matrix">Pentadiagonal</a></li> <li><a class="mw-selflink selflink">Permutation</a></li> <li><a href="/wiki/Persymmetric_matrix" title="Persymmetric matrix">Persymmetric</a></li> <li><a href="/wiki/Polynomial_matrix" title="Polynomial matrix">Polynomial</a></li> <li><a href="/wiki/Quaternionic_matrix" title="Quaternionic matrix">Quaternionic</a></li> <li><a href="/wiki/Signature_matrix" title="Signature matrix">Signature</a></li> <li><a href="/wiki/Skew-Hermitian_matrix" title="Skew-Hermitian matrix">Skew-Hermitian</a></li> <li><a href="/wiki/Skew-symmetric_matrix" title="Skew-symmetric matrix">Skew-symmetric</a></li> <li><a href="/wiki/Skyline_matrix" title="Skyline matrix">Skyline</a></li> <li><a href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse</a></li> <li><a href="/wiki/Sylvester_matrix" title="Sylvester matrix">Sylvester</a></li> <li><a href="/wiki/Symmetric_matrix" title="Symmetric matrix">Symmetric</a></li> <li><a href="/wiki/Toeplitz_matrix" title="Toeplitz matrix">Toeplitz</a></li> <li><a href="/wiki/Triangular_matrix" title="Triangular matrix">Triangular</a></li> <li><a href="/wiki/Tridiagonal_matrix" title="Tridiagonal matrix">Tridiagonal</a></li> <li><a href="/wiki/Vandermonde_matrix" title="Vandermonde matrix">Vandermonde</a></li> <li><a href="/wiki/Walsh_matrix" title="Walsh matrix">Walsh</a></li> <li><a href="/wiki/Z-matrix_(mathematics)" title="Z-matrix (mathematics)">Z</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Constant</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Exchange_matrix" title="Exchange matrix">Exchange</a></li> <li><a href="/wiki/Hilbert_matrix" title="Hilbert matrix">Hilbert</a></li> <li><a href="/wiki/Identity_matrix" title="Identity matrix">Identity</a></li> <li><a href="/wiki/Lehmer_matrix" title="Lehmer matrix">Lehmer</a></li> <li><a href="/wiki/Matrix_of_ones" title="Matrix of ones">Of ones</a></li> <li><a href="/wiki/Pascal_matrix" title="Pascal matrix">Pascal</a></li> <li><a href="/wiki/Pauli_matrices" title="Pauli matrices">Pauli</a></li> <li><a href="/wiki/Redheffer_matrix" title="Redheffer matrix">Redheffer</a></li> <li><a href="/wiki/Shift_matrix" title="Shift matrix">Shift</a></li> <li><a href="/wiki/Zero_matrix" title="Zero matrix">Zero</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Conditions on <a href="/wiki/Eigenvalues_and_eigenvectors" title="Eigenvalues and eigenvectors">eigenvalues or eigenvectors</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Companion_matrix" title="Companion matrix">Companion</a></li> <li><a href="/wiki/Convergent_matrix" title="Convergent matrix">Convergent</a></li> <li><a href="/wiki/Defective_matrix" title="Defective matrix">Defective</a></li> <li><a href="/wiki/Definite_matrix" title="Definite matrix">Definite</a></li> <li><a href="/wiki/Diagonalizable_matrix" title="Diagonalizable matrix">Diagonalizable</a></li> <li><a href="/wiki/Hurwitz-stable_matrix" title="Hurwitz-stable matrix">Hurwitz-stable</a></li> <li><a href="/wiki/Positive-definite_matrix" class="mw-redirect" title="Positive-definite matrix">Positive-definite</a></li> <li><a href="/wiki/Stieltjes_matrix" title="Stieltjes matrix">Stieltjes</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Satisfying conditions on <a href="/wiki/Matrix_product" class="mw-redirect" title="Matrix product">products</a> or <a href="/wiki/Inverse_of_a_matrix" class="mw-redirect" title="Inverse of a matrix">inverses</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Matrix_congruence" title="Matrix congruence">Congruent</a></li> <li><a href="/wiki/Idempotent_matrix" title="Idempotent matrix">Idempotent</a> or <a href="/wiki/Projection_(linear_algebra)" title="Projection (linear algebra)">Projection</a></li> <li><a href="/wiki/Invertible_matrix" title="Invertible matrix">Invertible</a></li> <li><a href="/wiki/Involutory_matrix" title="Involutory matrix">Involutory</a></li> <li><a href="/wiki/Nilpotent_matrix" title="Nilpotent matrix">Nilpotent</a></li> <li><a href="/wiki/Normal_matrix" title="Normal matrix">Normal</a></li> <li><a href="/wiki/Orthogonal_matrix" title="Orthogonal matrix">Orthogonal</a></li> <li><a href="/wiki/Unimodular_matrix" title="Unimodular matrix">Unimodular</a></li> <li><a href="/wiki/Unipotent" title="Unipotent">Unipotent</a></li> <li><a href="/wiki/Unitary_matrix" title="Unitary matrix">Unitary</a></li> <li><a href="/wiki/Totally_unimodular_matrix" class="mw-redirect" title="Totally unimodular matrix">Totally unimodular</a></li> <li><a href="/wiki/Weighing_matrix" title="Weighing matrix">Weighing</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">With specific applications</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Adjugate_matrix" title="Adjugate matrix">Adjugate</a></li> <li><a href="/wiki/Alternating_sign_matrix" title="Alternating sign matrix">Alternating sign</a></li> <li><a href="/wiki/Augmented_matrix" title="Augmented matrix">Augmented</a></li> <li><a href="/wiki/B%C3%A9zout_matrix" title="Bézout matrix">Bézout</a></li> <li><a href="/wiki/Carleman_matrix" title="Carleman matrix">Carleman</a></li> <li><a href="/wiki/Cartan_matrix" title="Cartan matrix">Cartan</a></li> <li><a href="/wiki/Circulant_matrix" title="Circulant matrix">Circulant</a></li> <li><a href="/wiki/Cofactor_matrix" class="mw-redirect" title="Cofactor matrix">Cofactor</a></li> <li><a href="/wiki/Commutation_matrix" title="Commutation matrix">Commutation</a></li> <li><a href="/wiki/Confusion_matrix" title="Confusion matrix">Confusion</a></li> <li><a href="/wiki/Coxeter_matrix" class="mw-redirect" title="Coxeter matrix">Coxeter</a></li> <li><a href="/wiki/Distance_matrix" title="Distance matrix">Distance</a></li> <li><a href="/wiki/Duplication_and_elimination_matrices" title="Duplication and elimination matrices">Duplication and elimination</a></li> <li><a href="/wiki/Euclidean_distance_matrix" title="Euclidean distance matrix">Euclidean distance</a></li> <li><a href="/wiki/Fundamental_matrix_(linear_differential_equation)" title="Fundamental matrix (linear differential equation)">Fundamental (linear differential equation)</a></li> <li><a href="/wiki/Generator_matrix" title="Generator matrix">Generator</a></li> <li><a href="/wiki/Gram_matrix" title="Gram matrix">Gram</a></li> <li><a href="/wiki/Hessian_matrix" title="Hessian matrix">Hessian</a></li> <li><a href="/wiki/Householder_transformation" title="Householder transformation">Householder</a></li> <li><a href="/wiki/Jacobian_matrix_and_determinant" title="Jacobian matrix and determinant">Jacobian</a></li> <li><a href="/wiki/Moment_matrix" title="Moment matrix">Moment</a></li> <li><a href="/wiki/Payoff_matrix" class="mw-redirect" title="Payoff matrix">Payoff</a></li> <li><a href="/wiki/Pick_matrix" class="mw-redirect" title="Pick matrix">Pick</a></li> <li><a href="/wiki/Random_matrix" title="Random matrix">Random</a></li> <li><a href="/wiki/Rotation_matrix" title="Rotation matrix">Rotation</a></li> <li><a href="/wiki/Routh%E2%80%93Hurwitz_matrix" title="Routh–Hurwitz matrix">Routh-Hurwitz</a></li> <li><a href="/wiki/Seifert_matrix" class="mw-redirect" title="Seifert matrix">Seifert</a></li> <li><a href="/wiki/Shear_matrix" class="mw-redirect" title="Shear matrix">Shear</a></li> <li><a href="/wiki/Similarity_matrix" class="mw-redirect" title="Similarity matrix">Similarity</a></li> <li><a href="/wiki/Symplectic_matrix" title="Symplectic matrix">Symplectic</a></li> <li><a href="/wiki/Totally_positive_matrix" title="Totally positive matrix">Totally positive</a></li> <li><a href="/wiki/Transformation_matrix" title="Transformation matrix">Transformation</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Used in <a href="/wiki/Statistics" title="Statistics">statistics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Centering_matrix" title="Centering matrix">Centering</a></li> <li><a href="/wiki/Correlation_matrix" class="mw-redirect" title="Correlation matrix">Correlation</a></li> <li><a href="/wiki/Covariance_matrix" title="Covariance matrix">Covariance</a></li> <li><a href="/wiki/Design_matrix" title="Design matrix">Design</a></li> <li><a href="/wiki/Doubly_stochastic_matrix" title="Doubly stochastic matrix">Doubly stochastic</a></li> <li><a href="/wiki/Fisher_information_matrix" class="mw-redirect" title="Fisher information matrix">Fisher information</a></li> <li><a href="/wiki/Projection_matrix" title="Projection matrix">Hat</a></li> <li><a href="/wiki/Precision_(statistics)" title="Precision (statistics)">Precision</a></li> <li><a href="/wiki/Stochastic_matrix" title="Stochastic matrix">Stochastic</a></li> <li><a href="/wiki/Stochastic_matrix" title="Stochastic matrix">Transition</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Used in <a href="/wiki/Graph_theory" title="Graph theory">graph theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Adjacency_matrix" title="Adjacency matrix">Adjacency</a></li> <li><a href="/wiki/Biadjacency_matrix" class="mw-redirect" title="Biadjacency matrix">Biadjacency</a></li> <li><a href="/wiki/Degree_matrix" title="Degree matrix">Degree</a></li> <li><a href="/wiki/Edmonds_matrix" title="Edmonds matrix">Edmonds</a></li> <li><a href="/wiki/Incidence_matrix" title="Incidence matrix">Incidence</a></li> <li><a href="/wiki/Laplacian_matrix" title="Laplacian matrix">Laplacian</a></li> <li><a href="/wiki/Seidel_adjacency_matrix" title="Seidel adjacency matrix">Seidel adjacency</a></li> <li><a href="/wiki/Tutte_matrix" title="Tutte matrix">Tutte</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Used in science and engineering</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cabibbo%E2%80%93Kobayashi%E2%80%93Maskawa_matrix" title="Cabibbo–Kobayashi–Maskawa matrix">Cabibbo–Kobayashi–Maskawa</a></li> <li><a href="/wiki/Density_matrix" title="Density matrix">Density</a></li> <li><a href="/wiki/Fundamental_matrix_(computer_vision)" title="Fundamental matrix (computer vision)">Fundamental (computer vision)</a></li> <li><a href="/wiki/Fuzzy_associative_matrix" title="Fuzzy associative matrix">Fuzzy associative</a></li> <li><a href="/wiki/Gamma_matrices" title="Gamma matrices">Gamma</a></li> <li><a href="/wiki/Gell-Mann_matrices" title="Gell-Mann matrices">Gell-Mann</a></li> <li><a href="/wiki/Hamiltonian_matrix" title="Hamiltonian matrix">Hamiltonian</a></li> <li><a href="/wiki/Irregular_matrix" title="Irregular matrix">Irregular</a></li> <li><a href="/wiki/Overlap_matrix" class="mw-redirect" title="Overlap matrix">Overlap</a></li> <li><a href="/wiki/S-matrix" title="S-matrix">S</a></li> <li><a href="/wiki/State-transition_matrix" title="State-transition matrix">State transition</a></li> <li><a href="/wiki/Substitution_matrix" title="Substitution matrix">Substitution</a></li> <li><a href="/wiki/Z-matrix_(chemistry)" title="Z-matrix (chemistry)">Z (chemistry)</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related terms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Jordan_normal_form" title="Jordan normal form">Jordan normal form</a></li> <li><a href="/wiki/Linear_independence" title="Linear independence">Linear independence</a></li> <li><a href="/wiki/Matrix_exponential" title="Matrix exponential">Matrix exponential</a></li> <li><a href="/wiki/Matrix_representation_of_conic_sections" title="Matrix representation of conic sections">Matrix representation of conic sections</a></li> <li><a href="/wiki/Perfect_matrix" title="Perfect matrix">Perfect matrix</a></li> <li><a href="/wiki/Pseudoinverse" class="mw-redirect" title="Pseudoinverse">Pseudoinverse</a></li> <li><a href="/wiki/Row_echelon_form" title="Row echelon form">Row echelon form</a></li> <li><a href="/wiki/Wronskian" title="Wronskian">Wronskian</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><b><span class="nowrap"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics_blue-p.svg" class="mw-file-description"><img alt="icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/16px-Nuvola_apps_edu_mathematics_blue-p.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/24px-Nuvola_apps_edu_mathematics_blue-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/32px-Nuvola_apps_edu_mathematics_blue-p.svg.png 2x" data-file-width="128" data-file-height="128" /></a></span> </span><a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a></b></li> <li><a href="/wiki/List_of_matrices" class="mw-redirect" title="List of matrices">List of matrices</a></li> <li><a href="/wiki/Category:Matrices" title="Category:Matrices">Category:Matrices</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a>: National <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q851512#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4811820-5">Germany</a></span></li></ul></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Permutation_matrix&oldid=1242522638">https://en.wikipedia.org/w/index.php?title=Permutation_matrix&oldid=1242522638</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Matrices" title="Category:Matrices">Matrices</a></li><li><a href="/wiki/Category:Permutations" title="Category:Permutations">Permutations</a></li><li><a href="/wiki/Category:Sparse_matrices" title="Category:Sparse matrices">Sparse matrices</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Use_American_English_from_January_2019" title="Category:Use American English from January 2019">Use American English from January 2019</a></li><li><a href="/wiki/Category:All_Wikipedia_articles_written_in_American_English" title="Category:All Wikipedia articles written in American English">All Wikipedia articles written in American English</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 27 August 2024, at 07:31<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Permutation_matrix&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-sscwj","wgBackendResponseTime":146,"wgPageParseReport":{"limitreport":{"cputime":"0.617","walltime":"0.893","ppvisitednodes":{"value":4636,"limit":1000000},"postexpandincludesize":{"value":53441,"limit":2097152},"templateargumentsize":{"value":2834,"limit":2097152},"expansiondepth":{"value":15,"limit":100},"expensivefunctioncount":{"value":3,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":39120,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 564.103 1 -total"," 28.36% 159.978 1 Template:Reflist"," 20.31% 114.594 1 Template:Short_description"," 18.45% 104.064 1 Template:Matrix_classes"," 18.36% 103.569 3 Template:Cite_book"," 17.09% 96.430 1 Template:Navbox"," 13.92% 78.506 2 Template:Pagetype"," 12.08% 68.135 9 Template:Rp"," 10.75% 60.625 9 Template:R/superscript"," 5.76% 32.496 2 Template:Harvnb"]},"scribunto":{"limitreport-timeusage":{"value":"0.289","limit":"10.000"},"limitreport-memusage":{"value":6098460,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFArtin1991\"] = 1,\n [\"CITEREFBrualdi2006\"] = 1,\n [\"CITEREFConwayBurgielGoodman-Strauss2008\"] = 1,\n [\"CITEREFNajnudelNikeghbali2013\"] = 1,\n [\"CITEREFZavlanosPappas2008\"] = 1,\n}\ntemplate_list = table#1 {\n [\"Authority control\"] = 1,\n [\"Citation\"] = 1,\n [\"Cite book\"] = 3,\n [\"Cite journal\"] = 1,\n [\"Harvnb\"] = 2,\n [\"Math\"] = 19,\n [\"Matrix classes\"] = 1,\n [\"Mvar\"] = 10,\n [\"Pi\"] = 15,\n [\"Refbegin\"] = 1,\n [\"Refend\"] = 1,\n [\"Reflist\"] = 1,\n [\"Rp\"] = 9,\n [\"Short description\"] = 1,\n [\"Sigma\"] = 4,\n [\"Tau\"] = 3,\n [\"Use American English\"] = 1,\n}\narticle_whitelist = table#1 {\n}\ntable#1 {\n [\"size\"] = \"tiny\",\n}\n"},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-rhzm7","timestamp":"20241124165136","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Permutation matrix","url":"https:\/\/en.wikipedia.org\/wiki\/Permutation_matrix","sameAs":"http:\/\/www.wikidata.org\/entity\/Q851512","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q851512","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-06-02T08:56:11Z","dateModified":"2024-08-27T07:31:11Z","headline":"matrices representing permutation of vector elements; with exactly one 1 per row and column"}</script> </body> </html>

CINXE.COM

Permutation matrix - Wikipedia