9
$\begingroup$

Let $A$ be the following matrix:$$A=\dfrac{1}{2}\ \left( \begin{array}{cccccccccc} -1 & -1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 & 1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 1 & -1 \\ \end{array} \right)$$ and $B=A+C$ with $C$ a matrix full of zeros, except the first $(2,2)$ block equal to $\begin{bmatrix} 1&1 \\ -1&-1\end{bmatrix}$:

$$B=\dfrac{1}{2}\ \left( \begin{array}{cccccccccc} \mathbf{1} & \mathbf{1} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \mathbf{-1} & \mathbf{-1} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 & 1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 1 & -1 \\ \end{array} \right)$$

Both $A,B$ are both orthogonal matrices with elements in $\{-\frac{1}{2},0,\frac{1}{2}\}$, hence each row and each column has exactly 4 non-zeros entries (the sum of the square of the entries of each row or column is 1). The characteristic polynomial of $A$ is $1+x^N$ and that of $B$ is $-1+x^N$ (here, $N=10$). $A,B,C$ do not commute.

$A,B$ are isometries, so is $A^n B^m$. I am trying to characterize $\ker(A^n B^m -I)$ for $(n,m)\in\mathbb{N}^2$.

From their characteristic polynomial, $B^N=I$ and $A^{2N}=I$ so it suffices to consider $n\leq 2N$ and $m\leq N$.

From experimental computations, it seems that "something happens": $A,B$ are made of $(2,2)$ blocks which are multiplied (there seems to be a structure of monoid) and translates to neighbour blocks.

The question is how to characterize the kernel of $A^nB^m-I$ (at least it's dimension) as a function of $n$ and $m$. This could be based on a basis in which $A$ and $B$ have a simple expression, but I did not succeed in identifying such a basis, despite the fact that $C=B-A$ is full of zeros (except 4 entries).

Edit Based on Armadillo Jim's answer, the question can also be written as finding the maximal invariant subspace of $A^n (DA)^m$ ($D$ is a block diagonal matrix of blocks $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ and $I_{N-2}$).

$\endgroup$
1
$\begingroup$

While I'm not sure if I'm getting at the question you really want to ask, I thought I'd add some observations here in the hope they help, and they're too long to post in a comment.

(1) $A$ and $B$ don't commute. Their commutator $AB-BA$ is non-zero. On the other hand, is it zero in its action on the last six coordinates.

(2) $A^m B^n$ is does not cover the case of arbitrary strings of $A$s and $B$s. That is, $A^3 B^2$ is different, say, from $ABABA$.

(3) You've noted an additive relationship between $A$ and $B$. But there's also a multiplicative one: $B = DA$ where $D$ is the matrix of an isometry (is an orthogonal matrix) too. Further, $D$ is symmetric (is the matrix of a reflection). See below.

(4) If what you want is indeed $\ker(A^m B^n - I)$, why not just enumerate those matrices, and use the periodicity of the matrices (as you've already found)? That's only 100 cases, plus reflections for $A^{10+m} = -A^m$.

(5) Another way of phrasing your problem is that you're looking for the eigenspace for the eigenvalue 1. (Or -1 if you want to reuse work for the flipped cases.) Either you can enumerate all eigenvalues for all 100 cases, or use specialized methods to look for the eigenvalue with largest real part.

Let: $$D=\left( \begin{array}{ccc} 0 & 1 & \vec{0}^T \\ 1 & 0 & \vec{0}^T \\ \vec{0} & \vec{0} & I \\ \end{array} \right)$$

where $I$ is the $8\times 8$ identity so that $B=DA$. Note that $D^2=I$ and $D=D^{-1}=D^T$; that is, $D$ is both an isometry (orthogonal) and a reflection (symmetric).

Using Sage:

def has_one(l):
    return sum([abs(x-1.0)<0.001 for x in l])
def has_minusone(l):
    return sum([abs(x+1.0)<0.001 for x in l])

A = 0.5*matrix(RDF, [
 [ -1, -1, 1, 1, 0, 0, 0, 0, 0, 0 ],
 [ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 ],
 [ 1, -1, 0, 0, 1, 1, 0, 0, 0, 0 ],
 [ -1, 1, 0, 0, 1, 1, 0, 0, 0, 0 ],
 [ 0, 0, 1, -1, 0, 0, 1, 1, 0, 0 ],
 [ 0, 0, -1, 1, 0, 0, 1, 1, 0, 0 ],
 [ 0, 0, 0, 0, 1, -1, 0, 0, 1, 1 ],
 [ 0, 0, 0, 0, -1, 1, 0, 0, 1, 1 ],
 [ 0, 0, 0, 0, 0, 0, 1, -1, 1, -1 ],
 [ 0, 0, 0, 0, 0, 0, -1, 1, 1, -1 ]
])
D = matrix(RDF, [
 [ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],
 [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
 [ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ],
 [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
 [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ],
 [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ],
 [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ],
 [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
])

foo = []
for i in range(10):
    for j in range(10):
        e = ( (A**i) * ((D*A)**j) ).eigenvalues()
        foo.append( (i,j,has_minusone(e),has_one(e)) )

for f in foo:
    print(f)

This gives the following table:

(0, 0, 0, 10)
(0, 1, 1, 1)
(0, 2, 0, 2)
(0, 3, 1, 1)
(0, 4, 0, 2)
(0, 5, 5, 5)
(0, 6, 0, 2)
(0, 7, 1, 1)
(0, 8, 0, 2)
(0, 9, 1, 1)
(1, 0, 0, 0)
(1, 1, 1, 1)
(1, 2, 0, 0)
(1, 3, 1, 1)
(1, 4, 4, 4)
(1, 5, 1, 1)
(1, 6, 0, 0)
(1, 7, 1, 1)
(1, 8, 0, 0)
(1, 9, 1, 9)
(2, 0, 2, 0)
(2, 1, 1, 1)
(2, 2, 2, 0)
(2, 3, 3, 3)
(2, 4, 2, 0)
(2, 5, 1, 1)
(2, 6, 2, 0)
(2, 7, 1, 1)
(2, 8, 2, 8)
(2, 9, 1, 1)
(3, 0, 0, 0)
(3, 1, 1, 1)
(3, 2, 2, 2)
(3, 3, 1, 1)
(3, 4, 0, 0)
(3, 5, 1, 1)
(3, 6, 0, 0)
(3, 7, 3, 7)
(3, 8, 0, 0)
(3, 9, 1, 1)
(4, 0, 0, 2)
(4, 1, 1, 1)
(4, 2, 0, 2)
(4, 3, 1, 1)
(4, 4, 0, 2)
(4, 5, 1, 1)
(4, 6, 4, 6)
(4, 7, 1, 1)
(4, 8, 0, 2)
(4, 9, 1, 1)
(5, 0, 0, 0)
(5, 1, 1, 1)
(5, 2, 0, 0)
(5, 3, 1, 1)
(5, 4, 0, 0)
(5, 5, 5, 5)
(5, 6, 0, 0)
(5, 7, 1, 1)
(5, 8, 0, 0)
(5, 9, 1, 1)
(6, 0, 2, 0)
(6, 1, 1, 1)
(6, 2, 2, 0)
(6, 3, 1, 1)
(6, 4, 6, 4)
(6, 5, 1, 1)
(6, 6, 2, 0)
(6, 7, 1, 1)
(6, 8, 2, 0)
(6, 9, 1, 1)
(7, 0, 0, 0)
(7, 1, 1, 1)
(7, 2, 0, 0)
(7, 3, 7, 3)
(7, 4, 0, 0)
(7, 5, 1, 1)
(7, 6, 0, 0)
(7, 7, 1, 1)
(7, 8, 2, 2)
(7, 9, 1, 1)
(8, 0, 0, 2)
(8, 1, 1, 1)
(8, 2, 8, 2)
(8, 3, 1, 1)
(8, 4, 0, 2)
(8, 5, 1, 1)
(8, 6, 0, 2)
(8, 7, 3, 3)
(8, 8, 0, 2)
(8, 9, 1, 1)
(9, 0, 0, 0)
(9, 1, 9, 1)
(9, 2, 0, 0)
(9, 3, 1, 1)
(9, 4, 0, 0)
(9, 5, 1, 1)
(9, 6, 4, 4)
(9, 7, 1, 1)
(9, 8, 0, 0)
(9, 9, 1, 1)

These are the dimensions of the kernel you're after.

There might be further insights to be gleaned from a decomposition into Givens rotations or Householder reflections. Also, $\det(DA)=-1$ whereas $\det(A)=+1$ so it might be worthwhile to split into even/odd cases in the power of $B=DA$.

$\endgroup$
  • $\begingroup$ I'll read carefully a bit later, but the reason why I'd like to avoid systematic exploration is that in pratice I have much larger n (typically 500). I asked the question with n=10 hoping I would be able to generalize the solution for larger $n$. I'll come back to you, thank you. $\endgroup$ – anderstood Jun 13 '16 at 3:44
  • $\begingroup$ As you show, there's something special about the dimension of the kernel, even if the sequence is not trivial. That's why I think there should be a nice approach to this problem. $\endgroup$ – anderstood Jun 13 '16 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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