Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A bisymmetric matrix is a square matrix that is symmetric about both of its main diagonals.

If $A$ is a bisymmetric matrix and I'm interested in solving $Ax=b$.

Are there techniques used to exploit this structure when solving the system of linear equations?

Note: I'm looking for techniques which exploit more than just the fact that the matrix is symmetric.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

The condition of symmetry about the antidiagonal says that $A$ commutes with reversal of coordinates. Call this operation $R$, so $R^2 = 1$ and $AR = RA$.
$R$ has a $+1$ eigenspace and a $-1$ eigenspace.

For any solution, you can project both $x$ and $b$ to the two eigenspaces, by averaging them with either their reversals or $-$ the reversals. You can get the induced action of $A$ on these (roughly if in odd dimension) half-size eigenspaces similarly. The two halves of $A$ are still symmetric, so you're left with the easier problem of solving two symmetric systems of equations in half the number of variables.

share|improve this answer
    
Excellent! This is a little surprising. The operation count by this method is $~2\frac{1}{3}(\frac{n}{2})^3 = \frac{1}{12}n^3$ (not including the memory savings). I was expecting at least $~\frac{1}{6}n^3$. Can you explain why this is? –  alext87 Sep 23 '10 at 14:58
1  
It's almost always simpler if you can separate variables cheaply. Basically you're eliminating the need to consider interactions between them. This is part of a more general method that usually helps if there is known symmetry. A compact (e.g. finite) group $G$ acting on a vector space canonically splits into subspaces according to the irreducible representations of $G$: the sum of all copies of a particular irreducible representation. Anything that commutes with the action of $G$ preserves this decomposition, so questions split into a usually easier collection of smaller subquestions. –  Bill Thurston Sep 23 '10 at 15:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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