Questions related to permutations, bijections from a finite (or sometimes infinite) set to itself.

**1**

vote

**0**answers

37 views

### clustering permutations by shared subsequences [on hold]

I have a question, stimulated by some biology, about comparing sets of permutations.
The problem
Let's think of genes on a bacterial chromosome as beads on a string - atomic, unique objects, with ...

**-5**

votes

**0**answers

31 views

### There are ten chairs in a row [closed]

There are ten chairs in a row.
In how many of these will two people be sitting in adjacent chairs?
I count 16. P1 and P2 must sit beside each other, adjacent, so there are only 8 chairs where that ...

**5**

votes

**0**answers

178 views

### Factorization of permutations into two factors with fixed number of cycles, plus a placement condition

In my recent work I have been led to consider the following type of permutation factorizations.
Let $\pi_1$ and $\pi_2$ be two fixed permutations, with disjoint support, i.e. $\pi_1$ acts on ...

**1**

vote

**0**answers

39 views

### Decomposing a matrix into the tensor product of a permutation and orthogonal matrix

Suppose I have a square matrix $A \in \mathbb{R}^{mn \times mn}$. I want to find
$$\arg \min_{P, Q} \|A - P \otimes Q\|_F$$
where $P$ is an $m \times m$ permutation matrix and $Q$ is an $n \times ...

**3**

votes

**2**answers

181 views

### Counting Specific Permutations of Elements in a Multiset

I have a question regarding counting permutations of a multiset's elements. The problem is the following:
Given a multi-set $M=\{0^{m}, 1^{n-m}\}$ the number of all possible permutations of its ...

**2**

votes

**2**answers

100 views

### On $XX'=I$ such that $AX=XB$ is true when $A,B\in\{0,1\}^{n\times n}$

Given real symmetric matrices $A,B\in\{0,1\}^{n\times n}$ is it true that $$AX=XB$$ has a solution of form $X$ a permutation matrix iff a solution with $XX'=I$ exists? We are over reals.
It is clear ...

**0**

votes

**0**answers

92 views

### On number of disjoint sets with small stack depth in a set of permutations

Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]),
What is ...

**12**

votes

**0**answers

176 views

### How does a permutation $P$ affect the singular value $\sigma_{\text{max}}(Q^\top P^\top Q)$ for orthogonal $Q$?

Let $q_i$ for $i=1,\ldots,m$ be the columns of the matrix $Q\in\mathbb{R}^{n\times m}$, $n\geq 2m$, which are pairwise orthonormal ( i.e.
$q_i^\top q_j = \begin{cases} 1 & \text{if}\quad i=j \\ 0 ...

**7**

votes

**2**answers

522 views

### Can all the sporadic groups be expressed as permutation groups based on a single big cycle?

Working on M11, I came up with that it can be generated using the following permutations:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[[2, 0, 1, 7], [3, 4, 5, 6]]
[[4, 0, 6, 7], [2, 3, 1, 5]]
[[0, 7], [4, 6], ...

**4**

votes

**2**answers

313 views

### Why does iterated indexing avoid cycles of length 5?

Start with a permutation $s_0$ of the numbers
$(1,\ldots,n)$, e.g., for $n=10$,
$s_0=(8,2,1,6,9,7,10,5,4,3)$.
Form $s_1$ by using the numbers in $s_0$ as indices into $s_0$.
So $s_1$ is composed of ...

**2**

votes

**2**answers

169 views

### $k$-th subset in order of increasing sum

I have an array of integers T[N] indexed from 1. For example T[1] = 1, T[2] = 4, T[3] = 5, T[4] = 9. Let's enumerate all subsets of this set in a certain order: increasing sum of the elements. In case ...

**3**

votes

**3**answers

136 views

### Characterizing (up to permutations) finite sequences of real numbers

Let $S=\{x_1,\cdots, x_N\}$ be a finite sequence of real numbers.
I am interested in characterizing the family of functions $F$ such that for any $f\in F$ the function
$$
c(\lambda) ...

**4**

votes

**1**answer

80 views

### Weights on cyclic orderings

Are there standard or known weights/metrics on cyclic orders?
Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a ...

**5**

votes

**1**answer

106 views

### What is the criterion for a matrix containing vectors and their permutations being invertible?

Consider the matrix $A\in\mathbb{R}^{m\times 2m}$. Let any arbitrary choice of $m$ columns of $A$ be linearly independent. Together with a permutation $P\in\mathcal{P_{2m}}$, one can build the matrix ...

**7**

votes

**1**answer

123 views

### Weighted Permutation Sum

I am trying to find out a closed-form formula (or a generating function at least) for the number of permutations $\sigma$ that satisfy $$ S = \sum_{i = 1}^{n} i\sigma(i)$$ for a given value of $S$. We ...

**2**

votes

**0**answers

119 views

### How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...

**8**

votes

**3**answers

468 views

### Is the Number of Carries in Integer-Addition Associative?

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions ...

**2**

votes

**0**answers

56 views

### symmetric points on symmetric spaces

Let $M$ by an $m$-dimensional symmetric space (or a general Riemannian manifold). The finite distinct points $p_1,p_2,\cdots,p_n\in M$ are said symmetric, if for any permutation $\sigma$ on ...

**1**

vote

**0**answers

38 views

### Finding optimal set of permutations [closed]

I have the following data set of a human population. The data set captures households and relationships of the persons living in those households. My problem is how to group the individuals into ...

**3**

votes

**1**answer

71 views

### convex hull of the set of permutations with one cycle

is there a way to describe the convex hull of the set of permutation matrices with exactly one non-trivial cycle?
or maybe I should ask for the convex hull of cycle matrices :
let $(i_{1},..,i_{k})$ ...

**0**

votes

**0**answers

46 views

### Sparse Matrix Reordering

Matrix reorderings are important for many direct solvers. Sometimes the objective
is to reduce the bandwith or the generated fill in by LU Decomposition.
I am interested in a reordering which reduces ...

**25**

votes

**5**answers

964 views

### How many rearrangements must fail to alter the value of a sum before you conclude that none do?

This will not be altogether unrelated to this earlier question.
For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...

**0**

votes

**0**answers

61 views

### Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in this sorting problem:
Input: a sequence $A$ of $2N$ positive integers.
...

**11**

votes

**1**answer

210 views

### A Collatz-like question about permutations

An answer to this question would provide an explicit counterexample to this question, but otherwise I don't know if it is interesting.
Consider all permutations $\pi$ on the natural numbers such that ...

**18**

votes

**1**answer

461 views

### Rearrangements that never change the value of a sum

I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...

**0**

votes

**1**answer

216 views

### A question on permutations

Given integers $1$ through $n$, let $S$ be set of ordering of integers that respect even alternating or reverse alternating permutations (https://en.wikipedia.org/wiki/Alternating_permutation) up to ...

**2**

votes

**0**answers

66 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...

**0**

votes

**0**answers

81 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...

**5**

votes

**0**answers

141 views

### Extrapolation between longest increasing and longest alternating subsequences

The question
When should we expect Tracy-Widom?
motivated me to post the following question, in which I have been
interested for a while. Let $f(n)$ be a function from the positive
integers to ...

**2**

votes

**0**answers

29 views

### Terminology for research on distributions of inner products

Consider a set of vectors $M$ from an inner product space $V$. The ordered set of inner products of all pairs of elements in $M$ uniquely characterizes $M$ up to isomorphism.
Suppose now that $V$ is ...

**5**

votes

**3**answers

704 views

### Permutations with all cycles odd length and permutations with all cycles even length

If $n$ is even, then the number of permutations of $n$ in which all cycles have odd length equals the number of permutations of $n$ in which all cycles have even length. This fact is easily proved, ...

**2**

votes

**0**answers

40 views

### Smooth bivariate functions identifiable under permutations

Consider a "smooth" $f : [0,1]^2 \to [0,1]$ and let $\pi : [n] \to [n]$ be a permutation of $[n] =\{1,\dots,n\}$. Let us define
$$
A^{f,\pi} := \Big( f\Big(\frac{\pi(i)}{n},\frac{\pi(j)}{n}\Big) ...

**2**

votes

**0**answers

118 views

### Permutation-invariant matrix representation

The question guide says that Mathoverflow is for research level mathematics. While I do not perform research in mathematics (I study quantum chemistry), I believe this question is research-level ...

**3**

votes

**1**answer

135 views

### Regarding left-to-right minima

Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minima in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is ...

**-1**

votes

**1**answer

163 views

### The name of a group of order 24 [closed]

I encountered a group $G =\langle(1,3,2,4),(3,5,4,6)\rangle\subseteq S_6$ in my study, but I do not know its name.
Let $f=(1,3,2,4)$ and $g=(3,5,4,6)$. We have $g^2=fg^2f$, and thus $\langle ...

**27**

votes

**3**answers

1k views

### Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power

I've known that one can arrange all the numbers from $1$ to $\color{red}{15}$ in a row such that the sum of every two adjacent numbers is a perfect square.
$$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$
...

**4**

votes

**1**answer

253 views

### Permutation polynomials mod $p$ of the form $(x+1)^n-x^n$

Among some permutation polynomials I've been studying, $f(x)=(x+1)^n-x^n$ is one of the polynomials that I cannot grasp.
Question : For a given odd prime $p$, how can we find every positive ...

**5**

votes

**1**answer

389 views

### When is a linear combination of permutation matrices unitary?

Question:
Let $P_\pi$ denote the matrix representation of permutation $\pi$. Consider a linear combination of all $n \times n$ permutation matrices
$$U := \sum_{\pi \in S_n} c_\pi P_\pi$$
where ...

**3**

votes

**0**answers

88 views

### Exact growth rate of Longest Increasing Subsequence expectation

Let $S_n$ be the symmetric group, $\pi\in S_n$ a uniformly random permutation and $L_n:=L_n(\pi)$ denoting the length of the longest increasing subsequence (LIS). We know that ...

**1**

vote

**0**answers

146 views

### Classifying 1 cycle permutation matrices

Given a permutation matrix that is not full rank, is there a linear algebraic and corresponding algebraic criterion to tell if matrix contains more than one disjoint non-trivial cycle or exactly one ...

**11**

votes

**3**answers

389 views

### Sets of points containing permutations - a Ramsey-type question

The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...

**3**

votes

**0**answers

53 views

### Is $LIS(\pi)+LIS(\sigma)+LIS(\sigma\pi^{-1})$ lower bounded?

In the title, $LIS$ stands for the length of longest increasing subsequence and Greek letters stand for permutations from symmetric group $S_n$.
Considering some cases such as ...

**1**

vote

**1**answer

68 views

### Are certain normal matrices circulant? (Part 2)

Let $\mathcal{F}$ denote the family of real normal matrices $A$ such that $
A^TA=\begin{pmatrix}
a & b \\
b & \ddots
\end{pmatrix}$, for $b>0$.
As a user observed in the solution of Part 1 ...

**3**

votes

**1**answer

159 views

### Hopf structures on “pictorial” descriptions of permutations

There is a well-known Hopf structure on permutations, due to Malvenuto and Reutenauer. Here, the F basis elements are permutations in one-line notation, the product of two permutations is their ...

**7**

votes

**2**answers

597 views

### Numbers with all N-digit prefixes divisible by N

In base 10, the number 3816547290 contains every digit exactly once. When I take the first N digits, that substring is divisible by N. For example, 381 is divisible by 3, 38165 is divisible by 5, etc. ...

**4**

votes

**0**answers

74 views

### Name for class of flattening permutations

Let $S_n$ be the symmetric group. For any sequence of numbers $y=[y_1,y_2,\cdots,y_k]$, define the flattening operation as $\mbox{flatt}_{k}(y)$ as a relabeling of $y_1,y_2,\cdots,y_k$ in terms of ...

**12**

votes

**1**answer

224 views

### Number of orders of $k$-sums of $n$-numbers

Suppose we have a $n$-element set $S$. Denote the set of its $k$-element subsets by $K$ ($|K|=\binom{n}{k}$).
If the elements of $S$ are real numbers then to each $k$-element subset we can associate ...

**14**

votes

**2**answers

332 views

### Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by ...

**4**

votes

**0**answers

237 views

### Polynomial dynamical systems

The question is somewhat related to the theory of permutation polynomials. Let $\mathbb{F}_p$ be a finite field of $p$ elements ($p$ is prime) and $\mathcal{V} = \mathbb{F}_p^2 = \{ (t_1,t_2)\::\: ...

**4**

votes

**1**answer

212 views

### Is there a geometric meaning of the Major index?

The actual question I want to ask is whether there is a geometric proof of this famous identity
$$\sum_{\sigma \in S_n} q^{\operatorname{inv} \sigma}=\sum_{\sigma\in ...