Spectrum of a function of permutations.

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Spectrum of a function of permutations.

G H J

Reveal topic tags

superior algebra

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3624 posts

#1 h Jun 7, 2025, 3:18 PM • 1 Y

Y by teomihai

Let $n$ be an even integer and $J_n$ be the $n\times n$ matrix of ones.
Let $S_n$ be the set of $n\times n$ permutation matrices, $f:P\in S_n\mapsto P^2+nP-J_n-I_n$
and $Z(P)=\{|\lambda|;\lambda\in spectrum(f(P))\}$ .
Show that $\bigcap_{P\in S_n} Z(P)$ is constitued of 2 elements to be determined.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

#2 h Jun 7, 2025, 4:12 PM

Y by

The intersection of all $Z(P)$ for $P\in S_{n}$ is the set $\{0,2n\}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3624 posts

#3 h Jun 8, 2025, 9:19 AM

Y by

@trangbui , no it isn't.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

#4 h Jun 8, 2025, 3:02 PM • 1 Y

Y by PikaPika999

loup blanc wrote:

@trangbui , no it isn't.

how do you know if you don't know how to solve it

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3624 posts

#5 h Jun 8, 2025, 6:55 PM • 1 Y

Y by PikaPika999

@ trangbui , I don't have a complete solution, but after computer calculations I'm sure the question is correct.
On the other hand, it's very easy to show that there is only one possible solution; just choose $P=I_n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

#6 h Jun 8, 2025, 8:29 PM • 1 Y

Y by PikaPika999

So what is your answer

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3624 posts

#7 h Jun 8, 2025, 10:24 PM

Y by

@ tranbui , please forget me .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3624 posts

#8 h Jul 7, 2025, 3:19 PM

Y by

A proposed solution. In the first part, we assume that $Z(P)$ is a set.
In the second one, we assume that $Z(P)$ is a list ( $Z(P)$ may contain repetitions).
$\textbf{Part 1.}$
i) The eigenvalues of $f(I_n)=nI_n-J$ are $0$ with multiplicity $1$ and $n$ with multiplicity $n-1$ .
Thus, to show that $\bigcap_{P\in S_n} Z(P)=\{0,n\}$ , it suffices to show that for every $P\in S_n$ , $0,n\in Z(P)$ .
ii) Let $U=[1,\cdots,1]^T$ . Note that $PU=U,JU=nU,J^2=nJ,PJ=JP=J$ .
Thus $f(P)U=0$ and $0\in Z(P)$ .
iii) To show that $n$ or $-n\in spectrum (f(P))$ , it suffices to show that $\det(Q)=0$ ,
where $Q=f(P)^2-n^2I_n=P^4+2nP^3+(n^2-2)P^2-2nP+(1-n^2)I_n-nJ$ .
Assume that (*) there is $u\in \mathbb{C}^n\setminus \{0\}$ be s.t. $Pu=u,Ju=0$ or $Pu=-u,Ju=0$ ;
then $Qu=0$ and $\det(Q)=0$ .
$\textbf{Lemma.}$ Let $n$ be even and $P\in S_n$ . If $1$ is a simple eigenvalue of $P$ , then $-1\in spectrum(P)$ .
$\textbf{Proof.}$ The eigenvalues of $P$ are roots of unity and $1\in spectrum(P)$ ; thus $\pm 1$ are the only possible real eigenvalues of $P$ .
If $1$ is a simple eigenvalue and $n$ is even, then $P$ admits $-1$ as an eigenvalue with multiplicity an odd number. $\square$
Case 1. $1$ is a multiple eigenvalue of $P$ ; then $dim(\ker(P-I_n))\geq 2$ and
$\ker(P-I_n)\cap\ker(J)\not= \{0\}$ and (*) is satisfied.
Case 2. $1$ is a simple eigenvalue of $P$ ; then $-1\in spectrum(P)$ and there is $u\not= 0$ s.t.
$Pu=-u$ ; one has $PJu=Ju=JPu=-Ju$ and $Ju=0$ and (*) is satisfied. $\square$
$\textbf{Part 2.}$ Now $Z(P)$ is a list and it remains to find $P\in S_n$ s.t. -for example-
(**) $-n$ is a simple eigenvalue of $Q$ and $n\notin spectrum(Q)$ .
We show that the matrix $P$ associated to the cycle $(1,2,\cdots,n)$ asks the question.
Let $v=[1,-1,\cdots,1,-1]^T$ ; then $Pv=-v,Jv=0$ and $Qv=-nv$ .

(**) is true when $n=2$ . Now $n\geq 4$ .
$\bullet$ Note that the characteristic polynomial of $P$ is $x^n-1$ and $PJ=JP$ ; then the eigenvalues of $Q$
are in the form $\lambda=r^2+rn-1$ or $\mu=r^2+rn-n-1$ , where $|r|=1$ and $n\geq 4$ .
$\bullet$ The real eigenvalues of $Q$ are obtained for real $r$ 's, that is, $r=\pm 1$ ; indeed, put $r=a+ib$ where $|a|\leq 1$ ; one has $r(r+n)\in\mathbb{R}$ , that is, $b=0$ or $a=\dfrac{-n}{2}$ ; only the first choice is possible.
$\bullet$ Thus the candidates are for $r=1$ : $\lambda=n,\mu=0$ and for $r=-1$ : $\lambda=-n,\mu=-2n$ .
We know that $0,-n$ are eigenvalues of $Q$ ; so these are the only real eigenvalues -with multiplicity 1- of $Q$ . Thus (**) is satisfied. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

#9 h Jul 7, 2025, 4:08 PM

Y by

loup blanc wrote:

@trangbui, please forget me.

ok it fine

This post has been edited 1 time. Last edited by trangbui, Jul 7, 2025, 4:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3624 posts

#10 h Jul 7, 2025, 7:15 PM

Y by

Thanks my friend.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a