Solve this 4x4 matrix using Cramer's rule

[sarahstar]

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.

[gorcee]

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?

[skullturf]

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?

[NathanielJ]

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" trickses 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?

[achan1058]

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" trickses 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.

[NathanielJ]

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?

[gorcee]

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