Matrix solution of linear systems

**Tempest** · September 2nd 2010, 04:20 AM

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.

**Ackbeet** · September 2nd 2010, 04:47 AM

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.

**Tempest** · September 2nd 2010, 04:49 AM

Interesting. What if I was just curious ?

**Ackbeet** · September 2nd 2010, 05:20 AM

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.

**Tempest** · September 2nd 2010, 05:38 AM

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

**Ackbeet** · September 2nd 2010, 06:22 AM

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.

**HallsofIvy** · September 2nd 2010, 09:09 AM

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.

**Tempest** · September 2nd 2010, 10:06 AM

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.

**HallsofIvy** · September 3rd 2010, 10:18 AM

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 [itex]x= (A*A)^{-1}A*B[/itex], and [itex](A*A)^{-1}A*[/itex] is called the "generalized inverse". If A itself has an inverse, then [itex](A*A)^{-1}= A^{-1}A*^{-1}[/itex] so that [itex](A*A)^{-1}A*= A^{-1}A*^{-1}A*= A^{-1}[/itex] the true inverse.

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

**Tempest** · September 5th 2010, 08:59 AM

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 [itex]x= (A*A)^{-1}A*B[/itex], and [itex](A*A)^{-1}A*[/itex] is called the "generalized inverse". If A itself has an inverse, then [itex](A*A)^{-1}= A^{-1}A*^{-1}[/itex] so that [itex](A*A)^{-1}A*= A^{-1}A*^{-1}A*= A^{-1}[/itex] 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

Thread: Matrix solution of linear systems

LinkBack

Thread Tools

Display

Matrix solution of linear systems

Similar Math Help Forum Discussions

Help with differential systems dealing with linearity and linear systems

Solutions of Linear Systems: Matrix Algebra

Systems of linear equations - no solution, unique solution, infinite solutions

[SOLVED] Elementary Linear Algebra, Systems of Linear Equations

Particular solution of linear systems

Search Tags