Solve this 4x4 matrix using Cramer's rule

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

Solve this 4x4 matrix using Cramer's rule

Postby sarahstar » Thu Apr 28, 2011 3:38 pm UTC

Solve this 4x4 matrix using Cramer's rule
(1-a1-a2 ; a1 ; a2 ; 0)
(b1 ; 1-b1-a2+c2 ; 0 ; a2-c2)
(b2 ; 0 ; 1-b2-a1+c2 ; a1-c1)
(0 ; b2+c2 ; b1+c1 ; 1-b1-c1-b2-c2)

all 4 rows equal zero and the variables to be found (going across the rows) are w, x, y and z.

When I tried to solve the first determinant I got 4 brackets with 3, 4, 4 and 5 elements in and the multiplying out got too confusing so I am not sure if it was right or not.

My teacher said Cramer's rule is the easiest way to solve so I want to do it by this method but I've never been taught it and I can't find an example using algebra.
sarahstar
 
Posts: 5
Joined: Sun Apr 24, 2011 11:09 am UTC

Re: Solve this 4x4 matrix using Cramer's rule

Postby gorcee » Thu Apr 28, 2011 3:46 pm UTC

First, just to assist with terminology, we don't "solve a matrix". A matrix is just a matrix.

What you have is a linear system in the form A\mathbf{x}=\mathbf{b}, where
A = \left(\begin{array}{cccc}
1-a_1-a_2 & a_1 & a_2 & 0 \\
b_1 & 1-b_1-a_2 + c_2 & 0 & a_2-c_2 \\
b_2 & 0 & 1-b_2-a_1+c_2 & a_1-c_1 \\
0 & b_2 + c_2 & b_1+c_1 & 1-b_1-c_1-b_2-c_2 \end{array}\right),


\mathbf{x} = \left(\begin{array}{c}w \\ x \\ y \\ z\end{array}\right),


\mathbf{b} = \left(\begin{array}{c}0 \\ 0 \\ 0 \\ 0\end{array}\right),


Cramer's rule is a terrible way to solve linear systems, as you have found out. Do you know Gaussian elimination?
gorcee
 
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC
Location: Charlottesville, VA

Re: Solve this 4x4 matrix using Cramer's rule

Postby skullturf » Thu Apr 28, 2011 4:23 pm UTC

A slight digression re Cramer's rule:

I've never used Cramer's rule in "real life" -- only on tests or assignments for a linear algebra class. I agree that it seems like a terrible way to solve linear systems.

However, suppose you have a fairly large linear system, and for some reason, you want to find the value of only one of the variables. Can Cramer's rule be a good thing to use in that case?
skullturf
 
Posts: 547
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago

Re: Solve this 4x4 matrix using Cramer's rule

Postby NathanielJ » Thu Apr 28, 2011 4:32 pm UTC

skullturf wrote:However, suppose you have a fairly large linear system, and for some reason, you want to find the value of only one of the variables. Can Cramer's rule be a good thing to use in that case?


Not really, no, unless the matrix has very specific sparsity properties that make the related determinants collapse.

Cramer's rule is a nice theoretical tool, but even if you only want the solution for one of the variables, you're better off doing Gaussian elimination. This is because the "naive" way of computing determinants (via cofactors or whatever "diagonal" tricks you may know) is O(n!), whereas Gaussian elimination computes *all* solution variables in O(n^3) time. There are faster ways of computing determinants, however -- ones that allow you to compute a determinant in O(n^3) time even... but those methods basically boil down to "do Gaussian elimination on the matrix", and if you're going to do that why not just solve the linear system that way in the first place?
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com
User avatar
NathanielJ
 
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Solve this 4x4 matrix using Cramer's rule

Postby achan1058 » Fri Apr 29, 2011 7:27 am UTC

NathanielJ wrote:
skullturf wrote:However, suppose you have a fairly large linear system, and for some reason, you want to find the value of only one of the variables. Can Cramer's rule be a good thing to use in that case?


Not really, no, unless the matrix has very specific sparsity properties that make the related determinants collapse.

Cramer's rule is a nice theoretical tool, but even if you only want the solution for one of the variables, you're better off doing Gaussian elimination. This is because the "naive" way of computing determinants (via cofactors or whatever "diagonal" tricks you may know) is O(n!), whereas Gaussian elimination computes *all* solution variables in O(n^3) time. There are faster ways of computing determinants, however -- ones that allow you to compute a determinant in O(n^3) time even... but those methods basically boil down to "do Gaussian elimination on the matrix", and if you're going to do that why not just solve the linear system that way in the first place?
There are faster stuff out there than just straight forward Gaussian elimination, for example to calculate something like the LU decomposition using Straussen (nobody uses Coppersmith–Winograd), and using that to compute both the determinant and to solve linear systems. IIRC the Big-O for determinant calculation and solving linear system is the same. As I am not familiar with the exact procedure, I won't comment on the time constants.
achan1058
 
Posts: 1791
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: Solve this 4x4 matrix using Cramer's rule

Postby NathanielJ » Sat Apr 30, 2011 2:01 am UTC

achan1058 wrote:There are faster stuff out there than just straight forward Gaussian elimination, for example to calculate something like the LU decomposition using Straussen (nobody uses Coppersmith–Winograd), and using that to compute both the determinant and to solve linear systems. IIRC the Big-O for determinant calculation and solving linear system is the same. As I am not familiar with the exact procedure, I won't comment on the time constants.


Absolutely. If you want to be really correct then: you can solve a linear system in O(n^w) time, where w is the exponent of matrix multiplication (currently upper-bounded by 2.376 via Coppersmith-Winograd as you mentioned). And similarly, the fastest known algorithm for computing determinants takes O(n^w) time. The point is just that if you have computed the determinant quickly (e.g., using Guassian elimination, Strassen, or whatever), then you likely have already transformed the system into a form that is trivial to solve, so why would you compute another n determinants when you could just be done right away?
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com
User avatar
NathanielJ
 
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Solve this 4x4 matrix using Cramer's rule

Postby gorcee » Sat Apr 30, 2011 12:43 pm UTC

If you're getting to the point that you're using C-W for Gaussian elimination, there's a good chance that you'll not have any problems handling this 4x4...

OP hasn't come back and said whether she's solved it or needs additional help, so let's not make it too complicated just yet :P
gorcee
 
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC
Location: Charlottesville, VA


Return to Mathematics

Who is online

Users browsing this forum: No registered users and 3 guests