Turn on thread page Beta
 You are Here: Home >< Maths

# Verifying matrix multiplication in O(n^2) watch

1. So, suppose I have three matrices A, B, and C, and it is claimed that either C = AB, or has "at most one error" (whatever that means). Apparently, I can verify that C = AB in time and fix the one error if I do find it. But I'm drawing a complete blank on how to do it.

I've searched online a little, but most of the results seem to be either probabilistic or quantum. The problem sounds suspiciously like parity checking, but I'm not sure that's what I'm supposed to do.
2. I'm not sure if this is exactly what you're after, but I think we can multiply by column vectors in .

The matrix AB-C will have (at most) one non-zero value, say t).

Computing (AB-C)(1,1,...1)^T = (0,...,t,...,0) (which gives the row of the error (3 O(n^2)) (and the value)

(1,1,...)(AB-C) = (0,...,t,...,0) gives the column, in 6O(n^2), ie O(n^2)
3. Ah, yes, that makes sense. I was thinking about testing it with some vectors, but I could only think of things which were ultimately equivalent to doing the whole matrix multiplication. Thanks!
4. (Original post by Zhen Lin)
Ah, yes, that makes sense. I was thinking about testing it with some vectors, but I could only think of things which were ultimately equivalent to doing the whole matrix multiplication. Thanks!
What course is this?
5. (Original post by SimonM)
What course is this?
"Alternative" Algorithms given by the maths department.
6. (Original post by ukdragon37)
"Alternative" Algorithms given by the maths department.
Is it good? I was going to go, but then didn't
7. (Original post by SimonM)
Is it good? I was going to go, but then didn't
Zhen Lin should answer, as due to various reasons I can't go. However I do keep informed of what's happening and I do the coding challenges online.

From what I've seen the course is very good (and is more advanced of what the CompSci version would be next term). You may be interested in the course website.

(Original post by Zhen Lin)
...
8. (Original post by SimonM)
Computing (AB-C)(1,1,...1)^T
Surely, for that, you'd have to compute AB? Which is O(n^3).
9. You can calculate A(B(1,1,...,1)^T) which is O(n^2)
10. (Original post by DFranklin)
You can calculate A(B(1,1,...,1)^T) which is O(n^2)
Aha, yes you can. Good thinking. Cheers.
11. (Original post by ukdragon37)
Zhen Lin should answer, as due to various reasons I can't go. However I do keep informed of what's happening and I do the coding challenges online.

From what I've seen the course is very good (and is more advanced of what the CompSci version would be next term). You may be interested in the course website.
It's certainly interesting. I've never done an algorithms course before though. A CompSci acquaintance says that some of the individual topics were done better in his department.

Turn on thread page Beta

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: February 11, 2010
The home of Results and Clearing

### 1,072

people online now

### 1,567,000

students helped last year
Today on TSR

### IT'S TODAY!

A-level results chat here

### University open days

1. London Metropolitan University
Sat, 18 Aug '18
2. Edge Hill University
Sat, 18 Aug '18
3. Bournemouth University
Clearing Open Day Undergraduate
Sat, 18 Aug '18
Poll
Useful resources

## Make your revision easier

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

Can you help? Study help unanswered threads

## Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE