1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
<html lang="en">
<head>
<title>Expressions Involving Permutation Matrices - Untitled</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="Untitled">
<meta name="generator" content="makeinfo 4.11">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Matrix-Algebra.html#Matrix-Algebra" title="Matrix Algebra">
<link rel="prev" href="Expressions-Involving-Diagonal-Matrices.html#Expressions-Involving-Diagonal-Matrices" title="Expressions Involving Diagonal Matrices">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
pre.display { font-family:inherit }
pre.format { font-family:inherit }
pre.smalldisplay { font-family:inherit; font-size:smaller }
pre.smallformat { font-family:inherit; font-size:smaller }
pre.smallexample { font-size:smaller }
pre.smalllisp { font-size:smaller }
span.sc { font-variant:small-caps }
span.roman { font-family:serif; font-weight:normal; }
span.sansserif { font-family:sans-serif; font-weight:normal; }
--></style>
</head>
<body>
<div class="node">
<p>
<a name="Expressions-Involving-Permutation-Matrices"></a>
Previous: <a rel="previous" accesskey="p" href="Expressions-Involving-Diagonal-Matrices.html#Expressions-Involving-Diagonal-Matrices">Expressions Involving Diagonal Matrices</a>,
Up: <a rel="up" accesskey="u" href="Matrix-Algebra.html#Matrix-Algebra">Matrix Algebra</a>
<hr>
</div>
<h4 class="subsection">20.2.2 Expressions Involving Permutation Matrices</h4>
<p>If <var>P</var> is a permutation matrix and <var>M</var> a matrix, the expression
<code>P*M</code> will permute the rows of <var>M</var>. Similarly, <code>M*P</code> will
yield a column permutation.
Matrix division <code>P\M</code> and <code>M/P</code> can be used to do inverse permutation.
<p>The previously described syntax for creating permutation matrices can actually
help an user to understand the connection between a permutation matrix and
a permuting vector. Namely, the following holds, where <code>I = eye (n)</code>
is an identity matrix:
<pre class="example"> I(p,:) * M = (I*M) (p,:) = M(p,:)
</pre>
<p>Similarly,
<pre class="example"> M * I(:,p) = (M*I) (:,p) = M(:,p)
</pre>
<p>The expressions <code>I(p,:)</code> and <code>I(:,p)</code> are permutation matrices.
<p>A permutation matrix can be transposed (or conjugate-transposed, which is the
same, because a permutation matrix is never complex), inverting the
permutation, or equivalently, turning a row-permutation matrix into a
column-permutation one. For permutation matrices, transpose is equivalent to
inversion, thus <code>P\M</code> is equivalent to <code>P'*M</code>. Transpose of a
permutation matrix (or inverse) is a constant-time operation, flipping only a
flag internally, and thus the choice between the two above equivalent
expressions for inverse permuting is completely up to the user's taste.
<p>Multiplication and division by permutation matrices works efficiently also when
combined with sparse matrices, i.e., <code>P*S</code>, where <var>P</var> is a permutation
matrix and <var>S</var> is a sparse matrix permutes the rows of the sparse matrix and
returns a sparse matrix. The expressions <code>S*P</code>, <code>P\S</code>, <code>S/P</code> work
analogically.
<p>Two permutation matrices can be multiplied or divided (if their sizes match), performing
a composition of permutations. Also a permutation matrix can be indexed by a permutation
vector (or two vectors), giving again a permutation matrix.
Any other operations do not generally yield a permutation matrix and will thus
trigger the implicit conversion.
</body></html>
|
