# Questions tagged [permutation-matrices]

A permutation matrix is a square matrix that has exactly one $1$ in each row and each column and $0$s elsewhere. Permutation matrices are orthogonal matrices.

217 questions
Filter by
Sorted by
Tagged with
11 views

• 581
15 views

### Decomposing Signed Permutations

Please, how do I decompose a signed permutation into simple transpositions? I need a concrete example to do this. I represented the signed permutation 3 -4 -1 2 in its cycle form (1 3 - 1 3) (2 -4 -2 ...
136 views

### Conditions for equivalence of $[A,BC] = 0$ and $[AB,C] = 0$

What are the most general conditions for which the commutation relations $[A,BC] = 0$ and $[AB,C] = 0$ equivalent? Alternatively, can it at least be shown to hold if $A$, $B$, and $C$ are all ...
32 views

### Need some help understanding Artin 1.5.10 proof on the product of permutations.

He writes: Why are both terms equal to zero unless i = qj? I really don't understand what's happening here. Edit: The ei,j terms, as usual, represent matrix units. The 'pi' and 'qj' refer to ...
• 125
102 views

### How to deduce: $T(x_1, \dots , x_i+x_j, \dots, x_i+x_j, \dots , x_n) = 0$?

studying about alternating multilinear applications I came across this expression. I understand that it represents the demonstration that an application T is antisymmetric (since it changes sign when ...
• 35
1 vote
193 views

### Prove that modified RBF function satisfies Mercer conditions.

Suppose that I have a modified RBF kernel function. $k(\mathbf{x},\mathbf{y}) = \exp{(-||\mathbf{x}-P\mathbf{y}||^2 })$ where $\mathbf{x},\mathbf{y}$ represent $d$ dimensional inputs and $P$ is the ...
• 21
40 views

### Invertible matrices acting on set of subspaces of the same dimension

I'm reading a paper and have stumbled upon the following phrases (everything over an arbitrary field $\mathbb{K}$): "As the natural action of $\operatorname{GL}_n(\mathbb{K})$ on the set of ...
• 713
1 vote
17 views

### Finding a Permutation Matrix of Two Matrices

So I have been painting polyhedra these days. I paint their vertices with different colors and then I paint the edges with colors that depend on the colors of the vertices in either end, and it turns ...
• 887
29 views

### Number of different types of n-permutation

Any $n$-permutation can by decomposed into the product of disjoint cycles. Assume there are $N_k$ k-cycle, the we can call $(N_1,N_2,\cdots,N_n)$ the type of a given permutation. My question is how ...
• 438
1 vote
66 views

### How many $3 \times 3$ matrices are sum of $r$ permutation matrices?

I'm trying to understand the solution of P.Stanley to the following: Let $H(r)$ be the number of $3 \times 3$ matrices of natural numbers that are the sum of $r$ permutation matrices $3 \times 3$. ...
23 views

### Counting row permutations that result in nonzero diagonals

Let $A$ be a binary square matrix in {$0,1$}$^{n\times n}$. What is the number of row permutations that will result in nonzero diagonals? I.e., the number of permutation matrices $P$ s.t. the diagonal ...
• 203
88 views

### Properties of matrices whose columns are permutations

I have a square matrix $G$ of size $n \times n$ in which each column is a random permutations of $[1,n]$, for example: 1 1 3 4 2 2 1 1 3 3 2 2 4 4 4 3 when $n=4$. ...
• 489
36 views

• 774
72 views

### Properties of a random permutation matrix

Given a uniformly sampled permutation matrix $\Pi\in\{0,1\}^{n\times n}$, what can we say about the matrix $E$ where $$\Pi = I + E,$$ where $I$ is the identity matrix. More precisely. what can we ...
• 774
25 views

I need to judge whether two $N\times N$ matrices $A$ and $B$ are permutation-similar or not; if we have $A_{ij}=B_{\sigma(i)\sigma(j)}$ where $\sigma(i)$ denote a permutation, we say $A\sim B$. Here \... 1 vote 1 answer 61 views ### Optimization problem over matrices (part 3) Background I'm working on the following linear program \begin{aligned} \max_{P} &\sum_{i=1}^{\min(m,n)} (MP)_{ii}\\ \text{st} \quad & 1_n'P=1_n'\\ &P 1_n= 1_n\\ &P_{ij}... • 699 0 votes 1 answer 50 views ### Permutation of a rank-r$matrix Let$M \in \mathbb{R}^{n \times m}$be a matrix of rank$r$. I believe that there always exist row and column permutation matrices$P$and$Q$such that $$P M Q = \left(\begin{array}{@{}c|c@{}} \... • 182 0 votes 0 answers 66 views ### Optimization problem over matrices (part 2) Background Yesterday I've asked some questions about a particular optimization problem that I have to resolve. I've found a simple solution which it turns out to be suboptimal (I have found a ... • 699 0 votes 1 answer 26 views ### Formulaic Representation of k-Permutations Out of a set S = \{1,2,3,4,5\}, I am picking elements 1 and 5. I then want to create all k=2-permutations from the remaining elements. For instance:$$ 1 \rightarrow \mathbf{2} \rightarrow \... • 163 2 votes 1 answer 136 views ### Lower bound on smallest diagonal element Let$\bf R$be an$m \times m$matrix with non-negative integer elements$r_{i,j}$,$0\leq r_{i,j} \leq n$and$n=km$(k is a positive integer), with the property$\sum_ir_{i,j}=\sum_jr_{i,j}=n$, i.e.,... • 37 0 votes 0 answers 65 views ### Is there existing an optimal permutation for data recovery? I am considering whether permuting the data$x^* \in \mathbb{R}^{n \times 1}$using a permutation matrix$P \in \mathbb{R}^{n \times n}$can enhance the recoverability of$x^*$in sparse recovery. I ... • 83 4 votes 1 answer 181 views ### The permutation matrices are the doubly stochastic matrices with the highest Frobenius norm In a 2013 talk, Alexandre d'Aspremont did claim the following: Among all doubly stochastic matrices, the rotations, hence, the permutation matrices, have the highest Frobenius norm I had never ... 1 vote 0 answers 44 views ### Determine eigenvalues and eigenvectors and exists a basis of eigenvectors Determine the eigenvalues and corresponding eigenvectors of $$A= \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$ Can you find a basis of$\mathbb{R}^3$... 0 votes 0 answers 46 views ### Permutation matrix inverse in$\{ P, P^2, P^3, \dots, P^n \}$Let$P$be an$ n \times n$permutation matrix. Does the list$\{ P, P^2, P^3, \dots, P^n \}$contain$P^{-1}$? If so, any proof without using group theory? • 299 1 vote 1 answer 172 views ### SVD: Picking U and V when singular values are repeated Is there a correct/stable way of dealing with repeated eigenvalues in S? I was working on a Moore-Penrose Inverse in a library for a programming language at work. The dummy matrix I picked turned out ... • 41 0 votes 0 answers 180 views ### Permutation matrix associated to a group action. In the following paper (Example 1.2) I don't understand how a group action is associated to a certain permutation matrix. We consider the cyclic group$G = \mathbb{Z}_6$and for$g \in G$we define ... • 1,953 0 votes 1 answer 49 views ### What does the notation$\epsilon_{a..d} 1.1.1.1$mean in the context of permutation matrices? I recently encountered the following paragraph in chapter 2 of The little Book of Permutation Matrices by Dennis Morris. Since they are square matrices, permutation matrices always have a determinant.... 0 votes 0 answers 55 views ### Product between two non-square permutation matrices Given a$n \times m$permutation matrix$X$(with$0 < n <= m$), I would like to show that$X'X$must be diagonal and$XX'=I$. How can I prove that? Note that a permutation matrix is a square (0,... • 121 2 votes 1 answer 85 views ### Find a permutation$X \in S_6$which satisfies the equation$\begin{pmatrix}1&2&3&4&5&6\\ 4&3&1&5&2&6\end{pmatrix} \circ X = \begin{pmatrix}1&2&3&4&5&6\\ 3&2&4&5&1&6\end{pmatrix}$... • 23 2 votes 1 answer 34 views ### Clarification on finite multiply transitive permutation groups and bounds on trace of associated permutation matrices Given a group$G$such that$G < S_n$,$G \neq A_n$, and$G$acts faithfully and transitively on the set$\Omega_n$where$n \geq 6$, is the following statement true? Given any non-identity ... • 317 0 votes 1 answer 48 views ### Can you find these sets of permutations? [closed] We have$n\geq2$a natural number and$S_{n}$the set of permutations with length n. Find the sets:$A=\left\{\sigma\in S_{n}\mid \exists\ r\geq1 \ and \ \sigma_{1},\sigma_{2},...,\sigma_{r}\in \ S_{...
• 1,281
1 vote
Suppose $S$ is the set of all $n\times n$ permutation matrices. For a matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$ define the set $P(\mathbf{A})$ as the set of all equal row and column permutations of ...