Freivaldâ €™ s Algorithm to check if a matrix is product of two | Python3 code to implement FreivaldaTMs Algorithm ; Function to check if ABx = Cx ; Generate a random vector ; Now comput B * r for evaluating expression A * ( B * r ) - ( C * r ) ; Now comput C * r for evaluating expression A * ( B * r ) - ( C * r ) ; Now comput A * ( B * r ) for evaluating expression A * ( B * r ) - ( C * r ) ; Finally check if value of expression A * ( B * r ) - ( C * r ) is 0 or not ; Runs k iterations Freivald . The value of k determines accuracy . Higher value means higher accuracy . ; Driver code
import random NEW_LINE N = 2 NEW_LINE def freivald ( a , b , c ) : NEW_LINE INDENT r = [ 0 ] * N NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT r [ i ] = ( int ) ( random . randrange ( 509090009 ) % 2 ) NEW_LINE DEDENT br = [ 0 ] * N NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( 0 , N ) : NEW_LINE INDENT br [ i ] = br [ i ] + b [ i ] [ j ] * r [ j ] NEW_LINE DEDENT DEDENT cr = [ 0 ] * N NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( 0 , N ) : NEW_LINE INDENT cr [ i ] = cr [ i ] + c [ i ] [ j ] * r [ j ] NEW_LINE DEDENT DEDENT axbr = [ 0 ] * N NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( 0 , N ) : NEW_LINE INDENT axbr [ i ] = axbr [ i ] + a [ i ] [ j ] * br [ j ] NEW_LINE DEDENT DEDENT for i in range ( 0 , N ) : NEW_LINE INDENT if ( axbr [ i ] - cr [ i ] != 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def isProduct ( a , b , c , k ) : NEW_LINE INDENT for i in range ( 0 , k ) : NEW_LINE INDENT if ( freivald ( a , b , c ) == False ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT a = [ [ 1 , 1 ] , [ 1 , 1 ] ] NEW_LINE b = [ [ 1 , 1 ] , [ 1 , 1 ] ] NEW_LINE c = [ [ 2 , 2 ] , [ 2 , 2 ] ] NEW_LINE k = 2 NEW_LINE if ( isProduct ( a , b , c , k ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT