# Thread: Matrix solution of linear systems

1. ## Matrix solution of linear systems

When r is less than n .

I have to find a way to do this, its a question on my upcoming exam and I've been looking in a whole lotta places. I found something, I'm just not 100% it's what I need.

Basically I need to find a way to solve a linear system where r is less than n with a matrix solution that's not the Gauss method, but the matrix equation method.

$AX = B$

$X = A^{-1}B$

Now, if I'm right about the upper equation being used for this method, what follows after it ? Do you guys know of a possible matrix solution of linear systems that starts out like that ?

I found one way in a book, it's basically used when det A == 0 . It's a formula that goes like this:

$X_{r} = A_{r}^{-1} * [B_{r} - A*X]$

The A and X in the above formula have the character ~ above them.

2. If this is a "question on [your] upcoming exam", then this problem is counting towards a grade. Forum policy is not knowingly to help with any problem that counts towards a grade.

3. Interesting. What if I was just curious ?

4. I'm not sure I understand the question. If you ask a question that does not count towards a grade, we'd be happy to help you with it.

Just for your reference, here is the rule I mentioned. It's #6, though all the rules would be good to look at.

5. I actually misunderstood the question, it seems it was just a general question about solving a system when r is less than n. I'm still curious about this, though, I've seen it once on some lectures but I didn't write it down. And I can't seem to remember if it has anything to do with the formula I wrote above

6. We're all glad you're curious about the problem. I don't plan to help you with this problem, for the reasons I've mentioned before. Post a different problem in a different thread that's not for a grade, and you can get help.

7. I might also point out that, in addition to saying "r is less than n", you ought to tell us what "r" and "n" mean! I suspect that one is the number of equations (number of rows of the matrix) and the other is the number of unknowns (number of columns of the matrix) but i have to guess that and, in any case, I don't know which is which.

8. Originally Posted by HallsofIvy
I might also point out that, in addition to saying "r is less than n", you ought to tell us what "r" and "n" mean! I suspect that one is the number of equations (number of rows of the matrix) and the other is the number of unknowns (number of columns of the matrix) but i have to guess that and, in any case, I don't know which is which.
Yeah, my bad. I guess there isn't a particular standard for all mathematicians as far as the use of these letters (I know it's different in different fields, but I'm talking about the same field - matrices) ?

R is the rank of the system matrix, and N is the number of unknowns.

9. Originally Posted by Tempest
When r is less than n .

I have to find a way to do this, its a question on my upcoming exam and I've been looking in a whole lotta places. I found something, I'm just not 100% it's what I need.

Basically I need to find a way to solve a linear system where r is less than n with a matrix solution that's not the Gauss method, but the matrix equation method.

$AX = B$

$X = A^{-1}B$

Now, if I'm right about the upper equation being used for this method, what follows after it ? Do you guys know of a possible matrix solution of linear systems that starts out like that ?
If r< n- that is if the rank is less than the number of rows, you cannot use this because A is not invertible- $A^{-1}$ does not exist.

I found one way in a book, it's basically used when det A == 0 . It's a formula that goes like this:

$X_{r} = A_{r}^{-1} * [B_{r} - A*X]$

The A and X in the above formula have the character ~ above them.
Does the book say what $A^\~$, $X^\~$, $A_r$, and $B_r$ mean?

You could do this: If A: $R^n\to R^m$ does not have an inverse then it maps all of $R^n$ into a sub space of $R^m$. There is no solution to Ax= B unless B happens to lie in that subspace (in which case there may be an infinite number of solutions). If B is not in the subspace then the best you can do is find x so that Ax is "closest" to B. To do that, drop a perpendicular from B to the subspace. Call vector, the vector in the range of A closest to B, B' and look at B- B'= B- Ax where x is such that Ax= B'. That vector is perpendicular to the subpace: <B- Ax, u>= 0 for all u in the subspace. But every vector in that subspace is of the form u= Av for some v because that subspace is the range of A, that is the same as <B- Ax, Av>= 0. Now define A~ to be the "adjoint" of A, the linear operator such that <v, Au>= <A*v, u> for all u in $R^n$ and all v in $R^m$ (for real matrices this is the transpose).

Then we have <B- Ax, Av>= <A*(B- Ax), v> where this inner product is on $R^n$ and v can be any vector in $R^n$/ In particular, v couls be A*(B- Ax) itself so we must have A*(B- Ax)= A*B- A*Ax= 0 or A*Ax= A*B. Now it may happen that A*A is invertible even if A itself is not. In that case we have $x= (A*A)^{-1}A*B$, and $(A*A)^{-1}A*$ is called the "generalized inverse". If A itself has an inverse, then $(A*A)^{-1}= A^{-1}A*^{-1}$ so that $(A*A)^{-1}A*= A^{-1}A*^{-1}A*= A^{-1}$ the true inverse.

Note that * throughout means the "adjoint", not multiplication.

10. Originally Posted by HallsofIvy
If r< n- that is if the rank is less than the number of rows, you cannot use this because A is not invertible- $A^{-1}$ does not exist.

Does the book say what $A^\~$, $X^\~$, $A_r$, and $B_r$ mean?

You could do this: If A: $R^n\to R^m$ does not have an inverse then it maps all of $R^n$ into a sub space of $R^m$. There is no solution to Ax= B unless B happens to lie in that subspace (in which case there may be an infinite number of solutions). If B is not in the subspace then the best you can do is find x so that Ax is "closest" to B. To do that, drop a perpendicular from B to the subspace. Call vector, the vector in the range of A closest to B, B' and look at B- B'= B- Ax where x is such that Ax= B'. That vector is perpendicular to the subpace: <B- Ax, u>= 0 for all u in the subspace. But every vector in that subspace is of the form u= Av for some v because that subspace is the range of A, that is the same as <B- Ax, Av>= 0. Now define A~ to be the "adjoint" of A, the linear operator such that <v, Au>= <A*v, u> for all u in $R^n$ and all v in $R^m$ (for real matrices this is the transpose).

Then we have <B- Ax, Av>= <A*(B- Ax), v> where this inner product is on $R^n$ and v can be any vector in $R^n$/ In particular, v couls be A*(B- Ax) itself so we must have A*(B- Ax)= A*B- A*Ax= 0 or A*Ax= A*B. Now it may happen that A*A is invertible even if A itself is not. In that case we have $x= (A*A)^{-1}A*B$, and $(A*A)^{-1}A*$ is called the "generalized inverse". If A itself has an inverse, then $(A*A)^{-1}= A^{-1}A*^{-1}$ so that $(A*A)^{-1}A*= A^{-1}A*^{-1}A*= A^{-1}$ the true inverse.

Note that * throughout means the "adjoint", not multiplication.
Damn, I didn't understand that post well. The way we are taught matrices here is pretty simplistic, I guess. I don't think this stuff was even applied in space like you're doing it in the first part of your post.

Anyway, let me try explain that formula using an example.
$x_1 - x_2 + 3x_3 = 1$
$2x_1 + x_2 - 3x_3 = 1$

$A^\~$ is a vector that contains the parameters that multiply with $x_3$, so in this case 3 and -3.

$X^\~$ is a vector that contains the unknowns that determine the other unknowns (in this case, it's only $x_3$.

$A_r$ is a 2x2 matrix with the multipliers of the other unknowns (1, -1, 2 and 1)

$B_r$ is another vector, with the numbers on the right side of the mentioned equation (1 and 1)

The 'r' in the subscript means reduced, and as I understood it, $A_r$ is the reduced matrix of A in the AX=B equation. So $A_r$ is the highest ranking matrix for which the determinant is different from 0.

Am I making any sense here ? :P