Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    2
    ReputationRep:
    So, suppose I have three n \times n 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 O(n^2) 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.
    Offline

    16
    ReputationRep:
    I'm not sure if this is exactly what you're after, but I think we can multiply by column vectors in O(n^2).

    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)
    • Thread Starter
    Offline

    2
    ReputationRep:
    Ah, yes, that makes sense. I was thinking about testing it with some vectors, but I could only think of O(n^3) things which were ultimately equivalent to doing the whole matrix multiplication. Thanks!
    Offline

    16
    ReputationRep:
    (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 O(n^3) things which were ultimately equivalent to doing the whole matrix multiplication. Thanks!
    What course is this?
    Offline

    13
    ReputationRep:
    (Original post by SimonM)
    What course is this?
    "Alternative" Algorithms given by the maths department.
    Offline

    16
    ReputationRep:
    (Original post by ukdragon37)
    "Alternative" Algorithms given by the maths department.
    Is it good? I was going to go, but then didn't
    Offline

    13
    ReputationRep:
    (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)
    ...
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (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).
    Offline

    17
    ReputationRep:
    You can calculate A(B(1,1,...,1)^T) which is O(n^2)
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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.
 
 
 
Poll
Who is your favourite TV detective?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

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

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.