5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – alext87
    Sep 23, 2010 at 14:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Thurston
    Sep 23, 2010 at 15:21

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.