Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
11 views

Permutation matrix as sum of orthogonal unit vectors

Let $P\in \mathbb{R}^n$ be a Permutation matrix that exchanges a pair of rows of indeces $1\leq p, q\leq n$. Is there any formula to parameterise $P$ as function of an elementary vector $e_i\in \...
Gino's user avatar
  • 372
1 vote
0 answers
44 views

Let a real symmetric matrix $M=Q \Lambda Q^T$. Under what conditions on $Q$ and $\Lambda$ is $M$ diagonal?

Let $M$ be a real symmetric matrix that has an eigendecomposition $M=Q \Lambda Q^T$, where $Q$ is an orthogonal matrix. Under what conditions on $Q$ and $\Lambda$ is $M$ diagonal? Thoughts: $M$ and $\...
kuzzooroo's user avatar
  • 581
0 votes
0 answers
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 ...
Abdulhafeez Ayinde Abdulsalam's user avatar
2 votes
1 answer
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 ...
xphileprof's user avatar
0 votes
0 answers
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 ...
idk's user avatar
  • 125
0 votes
1 answer
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 ...
MonkeyDL's user avatar
1 vote
0 answers
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 ...
flammmes's user avatar
3 votes
1 answer
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 ...
JBuck's user avatar
  • 713
1 vote
0 answers
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 ...
urquiza's user avatar
  • 887
0 votes
0 answers
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 ...
efsdfmo12's user avatar
  • 438
1 vote
1 answer
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$. ...
Armando Patrizio's user avatar
0 votes
1 answer
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 ...
graphitump's user avatar
0 votes
1 answer
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$. ...
fox's user avatar
  • 489
0 votes
1 answer
36 views

Invertible matrix subtracted by permutation matrices

Sorry for the vague title, but I do not know how to describe the question briefly. If any improvements are possible please edit. Given an arbitrary invertible matrix $A$ whose entries contains only $...
Covariant's user avatar
  • 482
2 votes
1 answer
111 views

Permutation equivariant Matrices

Im trying to find something out about the elements of permutation equivariant matrices. So matrices where if you switch somehting in your input vector the output switches as well. e.g. $$ \begin{...
elson1608's user avatar
  • 121
4 votes
0 answers
178 views

Linear sum assignment -- faster algorithms for a structured cost matrix?

The Hungarian algorithm for the linear sum assignment problem with dimension $n$ has complexity $O(n^3)$. Can the complexity be improved if one is able to assume that the cost matrix is structured? I ...
calmcc's user avatar
  • 251
1 vote
2 answers
55 views

Does this permutation matrix have a name?

Below are examples of the matrix I have in mind: $$ P_{2} = \begin{bmatrix} 1 & & & \\ & & 1 & \\ & 1 & & \\ & & & 1 \end{...
wintergreen_plaza's user avatar
1 vote
0 answers
36 views

Probability of a row in a permutation matrix being "correct"

Question: We have a uniformly sampled permutation matrix $\Pi\in\{0,1\}^{n\times n}$. What is the probability that the $i$th row in $\Pi$ is in the "correct" position, which means that the $...
Resu's user avatar
  • 774
2 votes
0 answers
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 ...
Resu's user avatar
  • 774
0 votes
0 answers
25 views

How to judge permutation-similarity from eigenvalues?

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 $\...
Takao Kotani's user avatar
1 vote
1 answer
61 views

Optimization problem over matrices (part 3)

Background I'm working on the following linear program \begin{equation} \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}...
matteogost's user avatar
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@{}} \...
Skywear's user avatar
  • 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 ...
matteogost's user avatar
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 \...
Wasserwaage's user avatar
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.,...
tako's user avatar
  • 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 ...
mse's user avatar
  • 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 ...
Rodrigo de Azevedo's user avatar
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$ ...
markus_tttt's user avatar
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?
Anirban 's user avatar
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 ...
Optimum's user avatar
  • 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 ...
James Arten's user avatar
  • 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....
EJoshuaS - Stand with Ukraine's user avatar
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,...
merch's user avatar
  • 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}$ ...
Millaray's user avatar
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 ...
Naiim's user avatar
  • 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_{...
Stefan Solomon's user avatar
1 vote
0 answers
55 views

Is there a short representation for the convex hull of all row and column permutations of a matrix?

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 ...
Kirschquark's user avatar
1 vote
1 answer
63 views

Matrix - exchanging elements

I want to show that it holds that $P_sG_k=\tilde{G}_kP_s, \ s\geq k$, where we get $\tilde{G}_k$ from $G_k$ by exchanging two entries $\ell_{j_1,k}$ and $\ell_{j_2,k}$ with $j_1,j_2\neq k$ ($j_1\neq ...
Mary Star's user avatar
  • 14k
0 votes
1 answer
39 views

Generalizing permutation matrices

I'm working on LU factorization that involves pivoting rows and I'm still trying to work my head around how to obtain the permutation matrices with ease. Say I want to interchange two rows. If I have ...
Dee's user avatar
  • 511
1 vote
1 answer
37 views

Finding a set of matrices that lets you read off order of multiplication

I am looking for a class of invertible matrices, $\{A_i\}$, where if I have a finite set of $n$ such matrices, $A_1,A_2,...,A_n$ that do not commute, then if I multiply them in some order to get a ...
user918212's user avatar
0 votes
0 answers
64 views

Are all matrices $A$ with $A^T=A^{-1}$ permutation matrices?

I know that all permutation matrices $A$ satisfy $A^T=A^{-1}$, but is the converse, all matrices $A$ with $A^T=A^{-1}$ are permutation matrices, also true? I believe it is true, but I haven't been ...
Matt MacKinnon's user avatar
1 vote
1 answer
70 views

Generating $S_n$ with subsets and permutations

Let $S_n$ be the symmetric group. My question is, does there exist a subset $A$ of $S_n$ such that for every element $\sigma \in S_n$, $\sigma$ can be "constructed" by taking subsets of the ...
user918212's user avatar
5 votes
1 answer
152 views

Non-negative integer matrix representations of finite groups

I wanted to know all the non-negative integer matrix (NIM) irreducible representations (irrep) of finite groups i.e. the homomorphisms $\varphi : G \to GL(n,\mathbb{Z}_{\geq 0})$. By irreducible NIM ...
Yaman Sanghavi's user avatar
1 vote
0 answers
13 views

Selecting independent features for random forest

Since I want each tree's selection to be as independent as possible, I've created a discrete optimization problem: $$A\in \lbrace 0,1 \rbrace^{x,y}$$ $$A [1]^T =[C]$$ $$A^{\star}=argmin_{A}\|AA^T\ - ...
deponce ye's user avatar
2 votes
2 answers
107 views

Is the cone of symmetric diagonally dominant matrices invariant under the conjugation by orthogonal matrices

Suppose A is a symmetric $n\times n$ matrix. $A$ is diagonally dominant (dd) if: $$ |A_{ii}| \ge \sum_{j=0, j\neq i}^n |A_{ij}| \ \ \forall i=1,2,\cdots ,n $$ Is $U^TAU$ dd for every dd $A$ and ...
khashayar's user avatar
  • 2,214
1 vote
1 answer
121 views

Multiplication in $S_4$ with cycle notation and permutation matrices

Solve the equation $(23)x^{-1}(124)=(34)^4$ in $S_4$. I'm a bit confused about which way I should go when multiplying. Using cycle notation I've been told to go from right to left, but I find it much ...
Walker's user avatar
  • 1,404
1 vote
1 answer
82 views

Min. Number of Sparse Matrix Elements to preserve Matrix Properties under Permutations

Given matrices $S \in \mathbb{R}^{G \times K}$, $Q\in \mathbb{R}^{K \times K}$ and $T \in \mathbb{R}^{G \times K}$ with $T = S \cdot Q$, I would like to find the minimum number of sparse elements in $...
N8_Coder's user avatar
2 votes
2 answers
91 views

How to find a matrix such that each row and col sums to 1 [closed]

I'm interested in finding a "soft" permutation matrix relating two equal sized sets $\{a_1, \dots, a_n\}$ and $\{b_1, \dots, b_n\}$. I have a distance function $d(a_i, b_j)$, so I can ...
raptortech's user avatar
1 vote
1 answer
120 views

Solving equations in permutation group

Given a relation on a permutation group $S_n$, I'm interested in solving for an unknown permutation. For a concrete example, let's say $\sigma_1=(12)\in S_3$ (in cycle notation), and the relation is $$...
levitopher's user avatar
  • 2,655
0 votes
0 answers
20 views

What set of matrices $X,Y$ satisfy $X \circ Y = X P Y$ for at least one permutation matrix $P$?

Suppose we have three $n \times n$ matrices $X,Y,P$ where $X,Y \in \mathbb{R^{n \times n}}$ and $P$ is a permutation matrix. Let us take $\circ$ to be the element-wise product between two matrices. ...
Galen's user avatar
  • 1,828

1
2 3 4 5