Results 1 to 10 of 10

Math Help - Matrix solution of linear systems

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    5

    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.
    Last edited by Tempest; September 2nd 2010 at 05:19 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    5
    Interesting. What if I was just curious ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2010
    Posts
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,412
    Thanks
    1328
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Sep 2010
    Posts
    5
    Quote Originally Posted by HallsofIvy View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,412
    Thanks
    1328
    Quote Originally Posted by Tempest View Post
    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.
    Last edited by HallsofIvy; September 3rd 2010 at 10:34 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Sep 2010
    Posts
    5
    Quote Originally Posted by HallsofIvy View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: February 13th 2011, 11:40 AM
  2. Solutions of Linear Systems: Matrix Algebra
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 31st 2011, 06:48 AM
  3. Replies: 1
    Last Post: March 24th 2010, 12:14 AM
  4. Replies: 7
    Last Post: August 30th 2009, 10:03 AM
  5. Particular solution of linear systems
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: April 19th 2009, 08:44 PM

Search Tags


/mathhelpforum @mathhelpforum