# How to get inverse of this matrix using least amount of space?

I'm working on a problem from a past exam and I'm stuck, so I'm asking for help. Here it is: $A = \frac12 \left[\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 \end{array}\right]$ find $\mathbf A^{-1}$.

My problem isn't the inverse matrix itself. We just get the determinant, see if it's zero or not, get the adjoint matrix and divide it by determinant.

My problem is space. As you can see, it's a 4x4 matrix meaning that I'd have to do 4x4 3x3 determinants to get the adjoint matrix plus 2 3x3 determinants to get determinant of the matrix. Now we get one A3 piece of paper for 6 problems. The problems are printed on one side and the other side is blank. This and the fact that inverse matrix is $A = \frac12 \left[\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 \end{array}\right]$

led me to believe that there's some catch that I do not see. Any ideas what could it be?

Also if someone could edit these matrices from MATLAB format into something that this site will parse would be great!

EDIT Unfortunately it seem that TeX code for matrices doesn't work here. Here's the matrix in MATLAB form, if anyone wants it A=(1/2)*[1,1,1,1;1,1,-1,-1;1,-1,1,-1;1,-1,-1,1];

EDIT 2 Answer by Jack Schmidt contains code for matrices.

-
use latex syntax for matrices, but remember to surround your script with a dollar sign or two. You can right-click and 'view source' on somebody else's post to see how they did it. – Tom Stephens Aug 10 '10 at 12:57
@Tom Stephens: matrices don't seem to work here, I tried it. – Tobias Kienzler Aug 10 '10 at 13:10
I can't get ti to display matrix, it only displays vector... I'll take a look at other questions, maybe someone got lucky. – AndrejaKo Aug 10 '10 at 13:17
Hey, that looks great! – Tom Stephens Aug 10 '10 at 14:15
@Tobias Kienzler Jack Schmidt posted code which makes matrices work! – AndrejaKo Aug 10 '10 at 15:02

I guess A is orthogonal and symmetric, so that tells you A−1 = AT = A, but uh, that's not a very common situation to my mind. Maybe someone else has a better "test-taking strategy" explanation, but me personally, I would just row reduce or whatever method you use in general.

An orthogonal matrix is defined to be a matrix whose transpose is its inverse. However, for us the better (almost) definition is a matrix whose rows (or columns) are orthogonal, as in, perpendicular. So (1,1,1,1) is orthogonal to (1,-1,1,-1) since their dot product is (1)(1)+(1)(-1)+(1)(1)+(1)(-1) = 1 - 1 + 1 - 1 is zero. You also should check that the length of the vector in each row is 1, $\sqrt{(1/2)^2 + (1/2)^2 + (1/2)^2 + (1/2)^2} = 1$ so good, but even if not, that part is easily fixed.

Sometimes you can tell just by looking that a matrix is orthogonal.

As far as parsing goes:

Here is the matrix:

$A = \frac12 \begin{pmatrix} 1 & 1 & 1 & 1 \\\\ 1 & 1 & -1 & -1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & -1 & -1 & 1 \end{pmatrix}$


$A = \frac12 \begin{pmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&1&-1\\1&-1&-1&1\end{pmatrix}$

Here is using the array environment:

$A = \frac12 \left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\\\ 1 & 1 & -1 & -1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & -1 & -1 & 1 \end{array}\right)$


$A = \frac12 \left(\begin{array}{rrrr}1&1&1&1\\1&1&-1&-1\\1&-1&1&-1\\1&-1&-1&1\end{array}\right)$

The backslashes get eaten by the markdown software, so you just double them.

-
What do you mean by orthogonal? Can you give me a link for that? We probably use different terminology here... Also row reduction is out of question because of space problems. – AndrejaKo Aug 10 '10 at 13:52
Oh, and thanks a lot for code for matrices! – AndrejaKo Aug 10 '10 at 13:56
I added the link to en.wikipedia.org/wiki/Orthogonal_matrix and gave a brief explanation. Basically, the rows are perpendicular, so AA^T is a diagonal matrix. The rows have length 1, so AA^T = 1, and A^T is the inverse of A. Since A is symmetric A is its own transpose, and so its own inverse. – Jack Schmidt Aug 10 '10 at 14:01
Thanks! This looks like the thing I was looking for! – AndrejaKo Aug 10 '10 at 14:08
There is a good reason that this matrix is orthogonal: Ignoring the $1/2$, this matrix is the character table of the group $\mathbb{Z}/2 \times \mathbb{Z}/2$. So othorgonality of the matrix follows from the orthogonality of characters en.wikipedia.org/wiki/Character_theory#Orthogonality_relations – David Speyer Aug 10 '10 at 14:21

If you have a $n\times n$ matrix $A$ , the inverse matrix $A^{-1}$ can be computed by using a compact method, that consists of the following steps:

1. Augment your matrix with the identity matrix $I$: $\left( A|I\right)$

2. Use Gaussian elimination to get an upper triangular matrix on the left and a matrix $J$ on the right: $\left( U|J\right)$, where $J=\left( J_{1}|J_{2}|\ldots |J_{n}\right)$.

3. To get the $n$ vector columns of the inverse matrix: $A^{-1}=\left( x_{1}|x_{2}|\ldots |x_{n}\right)$, solve for $x_{k}$, with $k=1,2,\ldots ,n$, $n$ systems of equations $U\cdot x_{k}=J_{k}$.

Note 1: in your problem $n=4$.

Note 2: there is a variant of this method called "Gaussian elimination with partial pivoting" that gives a better accuracy, when the entries are not rational numbers, which is not the present situation.

Until now I have not yet computed matrix $A^{-1}$ in this case. Instead I have used The Scientific Notebook (included in the Scientific Work Place) to find that your matrix satisfies $A=A^{-1}$:

$A=\begin{pmatrix}1/2&1/2&1/2&1/2 \\ 1/2&1/2&-1/2&-1/2\\1/2&-1/2&1/2&-1/2\\1/2&-1/2&-1/2&1/2\end{pmatrix}=A^{-1}$

-
Nice idea, unfortunately, we aren't supposed to know that so I don't think I'd get any points on test for doing something like that. Looks interesting though! – AndrejaKo Aug 11 '10 at 0:27
This method is well suited for automatic computation of the inverse matrix for $n$ relatively big. I am going to delete "the compactest I know" because there is another which is also compact. – Américo Tavares Aug 11 '10 at 0:40
"there is another which is also compact" - I presume you have the Crout scheme in mind... :) – J. M. Aug 11 '10 at 2:10
@J. Mangaldan, The Crout scheme (en.wikipedia.org/wiki/LU_decomposition) is new to me. I had thought on the following Theorem. If we apply elementary operations to the lines of the augmented matrix (A|I) and transform it into (I|B), then B = A^{−1}. – Américo Tavares Aug 11 '10 at 10:51

Have you tried reducing the matrix to row echelon form? Maybe my answer to this question: http://math.stackexchange.com/questions/1822/is-reducing-a-matrix-to-row-echelon-form-useful-at-all/1831#1831 could be helpful.

-
You answer is interesting (and the question is interesting too, we are also conditioned to use Cramer's rule as much as possible, so it's good to see reasons why it's a bad idea!), and in general is what I try to do, but how space efficient would it be? Also, can you provide a nice link to algorithm for using it? I can't understand Wikipedia's pseudo-code good enough. – AndrejaKo Aug 10 '10 at 21:01
You keep using the words "space efficient". By this, do you mean the number of variables needed? Gaussian requires only a single two-dimensional array (optionally a one-dimensional array if you pivot). – J. M. Aug 10 '10 at 22:00
I'm very sorry for not defining space efficient before! Honestly it looked obvious to me but after careful consideration, it's not as obvious as I thought it was. I mean it as in "least amount of writing", I explained in question why that's important for me. And please use this notation:@J. Mangaldan to talk to other users. For example, I didn't receive notification of your comment when you wrote it. If I remember correctly, first time someone comments, poster of the answer should receive notification and other people don't unless you explicitly specify their names. – AndrejaKo Aug 10 '10 at 22:42
@Agusti Roig Thank you very much for links! They were helpful. – AndrejaKo Aug 10 '10 at 22:51

Gauss/Jordan Elimination will do it. It'll let you find |A|^1 with out the bother of finding the determinant. Just augment your original matrix with the identity and let her rip.

On an aside, you can still deduce the determinant from the inverse.