4
$\begingroup$

Consider the matrix $D$, adjacency matrix of an undirected graph $G$ on $n$ vertices, with the notation that $d_{i,i}=0,\forall i$.

The matrices $A_i$ are constructed from Identity matrices, $I_{n*n}$ with $i^{th}$ column replaced with $i^{th}$ column of $D$.

I want to consider matrix $A=\prod_{s\in S} A_{s}$, where $S$ is a sequence containing all the entries in $\{1,2,\ldots, n \}$ at least twice. For example for $n=4$, $S$ can be (3,1,3,1,4,2,4,1) and in that case $A=A_{3}A_{2}A_{1}A_{3}A_{1}A_{4}A_{2}A_{4}A_{1}$. i.e., the only condition is that in the product every entry $k\leq n$ should occur at least twice.

I want to know that if there is a sequence $S$ such that $A$ has eigenvalue $1$, or that for every sequence $S$, $A$ doesn't have the eigenvalue $1$.

I tried examples by hand and also ran few simulations on matlab, but never found an $A$ with eigenvalue $1$.

I want to know if these kind of matrices have been studied before, or any remarks or hints on how to approach this.

$\endgroup$
1
  • 3
    $\begingroup$ I'm not quite sure this has anything to do with random-products or random matrices, right? At leas not in the sense of probability. Maybe you mean Arbitrary product? Any product? If so, I suggest you edit the title accordingly. $\endgroup$
    – Amir Sagiv
    Sep 5, 2016 at 5:19

1 Answer 1

11
$\begingroup$

In the case $n=4$ you could have $D = \pmatrix{0 & 0 & 0 & 1\cr 0 & 0 & 1 & 0\cr 0 & 1 & 0 & 0\cr 1 & 0 & 0 & 0}$, in which case $A_1 A_2 A_3 A_4 A_1 A_2 A_3 A_4 = \pmatrix{0 & 0 & 0 & 0\cr 0 & 0 & 0 & 0\cr 0 & 1 & 1 & 0\cr 1 & 0 & 0 & 1\cr}$ has eigenvalues $0$ and $1$, both with multiplicity $2$.

EDIT: In fact, in this case for any permutation of $A_1 \ldots A_4 A_1 \ldots A_4$ you always get the eigenvalues $0,0,1,1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.