# Solving Ag=b with non symmetric A

Following is a question that did not receive attention at math.SE at all. I am aware that is would be better suited there, but given its Economic background, perhaps it will get more attention here. If not, I'm happy to call this a failed attempt and delete it.

I need to solve $Ag=b$ for $b$, where $A$ is not symmetric.

$$A g = b \\ A = \left(\begin{matrix} A_1 \\ E_{IJ} \otimes \mathbb 1 \end{matrix}\right)$$

For some positive integers $I, J$: $A$ has size $(IJ\cdot J)\times IJ$, $g$ has size $IJ \times 1$, and $b$ has size $IJ \times 1$. $A$ is vertically stacked $A_1, A_2$, where $A_1$ is $IJ\times IJ$. $\mathbb 1$ is $J\times 1$ vector of ones, and $E$ is the identity matrix.

I need to solve this for $g$ on a computer for the case where $J$ small and $I$ large. I am fairly certain (through the way I get $A_1$ and $A_2$) that with $A_1$ being singular, my system of equations is exactly identifying $g$.

I'm used to the case where $A$ is symmetric and invertible. How do I proceed here?

• I don't understand. If $E_{IJ}$ is the (IJ x IJ) identity and $1$ is $1 X J$, then it seems that the kronecker product $E_{IJ} \otimes 1$ should be $IJ \times IJ^2$. If $A_1$ is $IJ \times IJ$, then there seems to be a conformity problem. – jmbejara Mar 6 '15 at 22:02
• I don't think that's correct. You probably mean that $1 \otimes E_{IJ}$ should be $J* IJ \times IJ$. If A is an m × n matrix and B is a p × q matrix, then the Kronecker product $A \otimes B$ is the mp × nq block matrix. – jmbejara Mar 6 '15 at 22:35
• @jmbejara yes, I agree - but the matrices are still conform. – FooBar Mar 6 '15 at 22:44
• Yes, now that the notation is fixed. So, what exactly is the question? If the system is exactly identified and you just want to solve this on a computer, A\b in Matlab will solve this using an appropriate method. Do you want something more? – jmbejara Mar 6 '15 at 22:53
• @jmbejara A is not symmetric and not invertible. I am not using Matlab. What would be an "appropriate method" here? Standard "linsolve" methods that I use in Python require invertibility. – FooBar Mar 6 '15 at 22:55

Maybe this helps. One method to do this is to use least squares (as was mentioned by @cc7768). Matlab does this by default when using the \ operator. This is also useful because it's sensible even if the system is overidentified as in the following example:

A = [1 22; 2 100; 7 6]
b = [1 2 5]'
A\b


produces

ans =

0.7108
0.0061


. In Python, this can be done with

import numpy
from numpy import linalg
A = numpy.matrix("1 22; 2 100; 7 6")
b = numpy.matrix("1 2 5").T
linalg.lstsq(A,b)[0]


which gives

matrix([[ 0.71084144],
[ 0.00611577]])


.

• Instead of Matlab you could stick with open source and use Julia ;) Python also has this functionality through scipy's solve method scipy.linalg.solve. – cc7768 Mar 6 '15 at 23:37