You are here:

Advanced Math/Determinants

Advertisement

Expert: - 4/7/2009


Question
Hello,

I'm a 25 year old computer science student. There's a question regarding determinants that I've been working on for a whole day and haven't been able to solve.

Given a square matrix "A" n*n containing only "ones" and "minus ones", I need to prove that exists an integer K so:
det(A) = K*(2^(n-1))

I've tried induction and thought I came close but reached a dead end after extracting 2^(n-1) from the summary. I needed to prove that whatever was left in the summary after the extraction - is even. So maybe induction is not the way.

Thanks,
Or

Answer
Consider putting this matrix in upper triangular form so that the determinant is the product of all of the diagonal elements.

If we start with a 2x2 matrix, lets leave the first row alone.
To get a zero in the start of the second row, either add the first row or subtract the first row.  The choices for the second element are 1-1, -1+1, -1-1, or 1+1.  As you can see, the results are 0, 0, -2, or 2.  When the zero is gotten, the matrix rows are not linearly independent and the determinant is 0.  If this is not the case, a 2 or -2 is gotten.  So for a two by two matrix, the result works since the determinant is 2 or -2, which is 2^1 with a plus or minus sign.

Consider and nxn matrix.  As was stated in the last paragraph, after eliminating all cells in the first column, the entire matrix in the 2nd row and farther down is full of -2's, 0's, and/or 2's.
We can then take out the first row and first column and say that the determinant is the first element in the first row times the determinant of the resulting matrix.  We can also factor out a 2, leaving only -1's, 0's, and /or 1's in each position.

If the matrix is now a 2x2, then the determinant is plus or minus 2.  Note that the determinant of the 3x3 was twice this value, so it's plus or minus 4.

In other words, if we have an nxn matrix, when we reduce the size by 1, we multiply the determinant by 2 as we factor out the two, leaving a matrix that is (n-1)x(n-1).  Eventually we'll get down to a 2x2 and the determinant of 2^(n-2)*determinant(2x2).  In the first paragraph, the determinant of the 2x2 was shown to be -2, 0, or 2.
So the overall determinant is 2*2^(n-2) = 2^(n-1), with a plus or minus thrown in.

Advanced Math

All Answers

Answers by Expert:

Ask Experts

Volunteer

Scott A Wilson

Expertise

I can answer any question in general math, arithetic, discret math, algebra, box problems, geometry, filling a tank with water, trigonometry, pre-calculus, linear algebra, complex mathematics, probability, statistics, and most of anything else that relates to math. I can even tell you it takes me over 2,000 steps to go a mile, but is that relevant?

Experience

Experience in the area; I have tutored people in the above areas of mathematics for almost two years in AllExperts.com. I have tutored people here and there in mathematics since before I received a BS degree almost 25 years ago. In just two more years, I received an MS degree as well, but more on that later. I tutored at OSU in the math center for all six years I was there. Most students offering assistance were juniors, seniors, or graduate students. I was allowed to tutor as a freshman. I tutored at Mathnasium for well over a year. I worked at The Boeing Company for over 5 years. I received an MS degreee in Mathematics from Oregon State Univeristy. The classes I took were over 100 hours of upper division credits in mathematical courses such as calculus, statistics, probabilty, linear algrebra, powers, linear regression, matrices, and more. I graduated with honors in both my BS and MS degrees. Past/Present Clients: College Students at Oregon State University, various math people since college, over 7,500 people on the PC from the US and rest the world.

Publications
My master's paper was published in the OSU journal. The subject of it was Numerical Analysis used in shock waves and rarefaction fans. It dealt with discontinuities that arose over time. They were solved using the Leap Frog method. That method was used and improvements of it were shown. The improvements were by Enquist-Osher, Godunov, and Lax-Wendroff.

Education/Credentials
Master of Science at OSU with high honors in mathematics. Bachelor of Science at OSU with high honors in mathematical sciences. This degree involved mathematics, statistics, and computer science. I also took sophmore level physics and chemistry while I was attending college. On the side I took raquetball, but that's still not relevant.

Awards and Honors
I earned high honors in both my BS degree and MS degree from Oregon State. I was in near the top in most of my classes. In several classes in mathematics, I was first. In a class of over 100 students, I was always one of the first ones to complete the test. I graduated with well over 50 credits in upper division mathematics.

Past/Present Clients
My clients have been students at OSU, people nearby, friends with math questions, and several people every day on the PC, and you're probably make one more.

©2012 About.com, a part of The New York Times Company. All rights reserved.