6
$\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
7
$\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
    Commented 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
    Commented Sep 23, 2010 at 15:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .