/sci/ - Science & Math

[Anonymous No.4084266]

I have an algorithm question Im a bit stuck on and was wondering if anyone had any idea on how to solve it. I think the answer is supposed to be pretty simple, but I cant think how to do it.

Say we have 3 matrices of n*n size. How can we check A*B = C without multiplying A and B.

Anyone got a clue how to do it?

[Anonymous No.4084268]

>>4084266
Uhh, no. You multiply it. You don't need to store the full result of the multiplied matrix at a single point in time, but you do need to calculate it.

[Anonymous No.4084277]

>>4084268
Alternatively, if we know something about the input set, perhaps there are asymptotically faster methods. Not sure. I think not, but not sure.

In the end, the algorithm will have to contain basically the code to do matrix multiplication, but it's possible that a good heurestic will remove some cases before you get there.

[almostphysicist No.4084281]

>>4084266
C/B = A?

Or perhaps this is something to do with determinants?

[almostphysicist No.4084287]

Or maybe you can diagonalize them or convert them to row echelon form and quickly check if those simplified forms would lead to non-zero values in C where you would expect 0?

[Anonymous No.4084307]

OP here.

Its actually for a computing class so I dont think we need a lot of math involved... its more the algorithm you can come up with.

I was thinking that you could possibly make a random binary vector x of size n. Then compute B*x=y. Then calculate A*y and C*x and see if the results are the same. Then if the matrices are the same, then there is a 1/2 chance that A*B = C and 1/2 chance that A*B != C (because we used a binary vector). To amplify the probability that the answer we return is right, we can do this same process with a random binary vector a few times.

Does that sound right, or am I "cheating" with the B*x = y then multiplying A*y?

[Anonymous No.4084314]

>>4084307
Anything wrong with just doing the multiplication, then comparing for equality?

[Anonymous No.4084328]

>>4084314

No. It says specifically to do it without multiplying A and B.

I think its because doing it without multiplying A and B together is faster..... but Im not sure if my algorithm is allowed.

[Anonymous No.4084344]

>>4084328
>No. It says specifically to do it without multiplying A and B.

Over the full set of possible matrices, this is impossible. I would complain to your professor.

If your algorithm has to return the right answer every time, and the algorithm has to work on any arbitrary pair of matrices, then it has to do matrix multiplication. Perhaps it could apply heurestics or rules before doing it, but the worst case would end in doing the matrix multiplication.

I would query your professor whether he actually meant: "Your program must never have the whole multiply result resident at any particular time", because then this is a solvable problem.

[Anonymous No.4084350]

>>4084344
Maybe he's playing some other kind of word game where if you use a different structured algorithm that actually does compute the multiplication, but doesn't do it in the conventional sense, then that counts? This is a bullshit assignment.

Btw, college grad here, making 100k a year programming.

[Anonymous No.4084370]

>>4084350
To continue, maybe there's some other equivalent mathematical transformation to do that?

It's just such bullshit. This is /never/ an assignment you would actually get. In the real world, we program to requirements, and this will never, ever be a requirement.

And if my PM gave me this requirement, I would give pushback until it went away or it morphed into a more reasonable requirement, like memory requirement, runtime requirement, code maintenance requirement, extensibility, and so on.

[Anonymous No.4084425]

Assuming det(B) != 0 check if A = CB^-1?

[Anonymous No.4084458]

>>4084350
>if you use a different structured algorithm that actually does compute the multiplication, but doesn't do it in the conventional sense

OP here. I think that is what he meant. I already know there is one unconventional way of doing matrix multiplications called Strassen's method which involves 7 multiplications instead of 8 on a 2*2 matrix, but I dont think that that is the answer.

[Anonymous No.4084492]

The worst case will always require doing the mutliplication, but we can remove certain possibilities on the way.
|A| |B| =/= |C| => AB =/= C
We can then check all of the matrix groups. They're closed, so if A and B are in O(n), but C isn't, then AB =/= C, again.
Eventually, however, you will need to multiply them and check.
You could simplify this process by using some of the quantities and qualities found when computing their groups.

[Anonymous No.4084495]

http://en.wikipedia.org/wiki/Z-order_%28curve%29
Perhaps?