You are here:

Advanced Math/drawing conclusions

Advertisement

Expert: - 2/4/2009


Question

penny
Please see the attached image. This problem requires me to figure out an algorithm is not correct and why. Can you explain how you would do this? And why Dr. Smeadly made an error?

Answer
The simplest way that I can find to do it is this.
Right down the matrix, and then circle each element in the
middle diagonal, since this is the first set of elements to
choose.

At the top, right down the value of the element chosen in
that column.  On the side, right down the value of the element
chosen in that row.  Below each of the noncirlced values in the
table, subtract off the average of the elements added together
that are in that row and column.  Choose the largest negative
value and switch that row and column.  Repeat this process
until you get no negatives.

I will offer you a 3x3 example.  Lets take the matrix
2  5  3
4  9  2
5  8  6
and start off choosing the elements down the diagonal, namely,
2, 9, and 6.  In the top row (above the table), we'll put
2, 9, and 6.  In the side column (to the left of the table),
we'll put 2, 9, and 6.

Row 1
Element 1: circled, so we'll ignore that one.

Element 2: value is 5, and 5 - (2+9)/2 = -0.5,
 so that's a possibility of one we want to add to the set up.

Element 3: value is 3, and 3 - (2+6)/2 = -1,
which is greater the -0.5, so now maybe that's the one to add.

Row 2
Element 1: 4 - (9+2)/2 = -1.5, which is the greatest so far,
so maybe it's this one.

Element 2: circled, so we'll ignore that one

Element 3: 2 - (9+6)/2 = -5.5, so that really looks like the one
to add in to the set.  Ignore those first three comments about
which one to add.

Row 3:
Element 1: 5 - (6+2)/2 = 1, ignore those positive values.

Element 2: 8 - (9+6)/2 = 0.5, we'll ignore that one to.


So the element to add is row 2, column 3 (2,3).
That means we'll take away element (2,2) and element (3,3).  
That means we'll add element (3,2).

Looking back at the original matrix, circle element
(1,1) { value is 2 },
(2,3) { value is 2 }, and
(3,2) { value is 8 }.

Computing new table differences:
row 1, col 1: ignore,
row 1, col 2: 5 - *8+2)/2 = 0,
row 1, col 3: 3 - (2+2)/2 = 1,

row 2, col 1: 4 - (2+2)/2 = 0,
row 2, col 2: 9 - (8+2)/2 = 4,
row 2, col 3: ignore,

row 3, col 1: 5 - (2+8)/2 = 0,
row 3, col 2: ignore, and
row 3, col 3: 6 - (8+2)/2 = 1.

There are no negative values, so that's the optimal solution.
Note elements (1,1) and (3,2) could be traded for
elements (1,2) and (3,1).  The value would be 2+8 or 5+5.
Either way, that gives 10 as the result with an overall
total of 12.

Take a bunch of paper in hand and now attack that 10x10 matrix.
Circle the elements chosen.  From each of the other elements in that matrix, the lower number for that cell in each operation should be
the value in that cell - (number circled in column plus number
circled in row)/2.

I believe in the third row, ninth column, you'll get a
1 - (14+21)/2 = -16.5, and this is the smallest (biggest
negative) element.  Instead of the route having element (2,2)
and (9,9), it will now have (2,9) and (9,2).

Switch the nine and two above the matrix in the top row and
beside the matrix in the left row.  Switch the circles from
(2,2) and (9,9) to (1,9) and (9,2).  Recompute all the
differences and see what the next negative is.

Repeat this process until there are no negative values.
The minimum value is the sum of all the circled elements.

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.