0
$\begingroup$

Here, n = no. of rows and m = no. of columns

Suppose, there are three matrices - A[3][2] : {{1,2},{3,4},{5,6}} ; B[3][2] : {{1,2},{3,4},{5,6}} ; C[3][2] : {{2,1},{3,4},{5,6}} . Here A=B , A!=C and B!=C .

So, task is to check equality between all possible combinations of 2-dimensional matrices from a given set of matrices with time complexity less than O(n^m) .Here the possible combinations are (A,B) , (A,C) and (B,C).

( As part of the solution :

Matrix to matrix comparison is costly .So these matrices have to be converted into 'something' which results less comparison time . I think if I can convert/represent the matrix as a value/string/1-dimensional array , then equality comparison will be less costlier . My question is how to convert/represent ? If it can be solved by hashing how to solve this exactly ? )

NOTE : No. of 2-dimensional matrices and their sizes are not fixed. In my problem scenario no. of 2-dimensional matrices are been generated gradually which can be of any size. Cant predict how many matrices of which size will be generated . Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .

Improve this question
$\endgroup$
3
  • $\begingroup$ What is $n$? How many matrices are there? What is the size of the matrices? Are they dense/sparse? $\endgroup$
    – orlp
    Commented Mar 4, 2020 at 10:33
  • $\begingroup$ I have edited my question. Please check it . @orlp $\endgroup$
    – ssarmah
    Commented Mar 4, 2020 at 12:09
  • 1
    $\begingroup$ You are asking whether two matrices can be checked for equality in less than $O(nm)$ time (which is trivially impossible without preprocessing) but it sounds more like your actual problem is to partition matrices into equivalence classes by equality (which would normally be solved by hashing, which reduces the number of equality comparisons that need to be performed). $\endgroup$
    – Aaron Rotenberg
    Commented Mar 4, 2020 at 14:29

2 Answers 2

Reset to default
2
$\begingroup$

Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .

It seems it would be easiest to store the previously seen matrices in a Trie. You can then test whether the given input matrix is equal to any of the previous matrices in $O(nm)$, regardless of how many previous matrices there are. This is the best you can do, since you must examine each element of the matrix at least once. You can't get an individual comparison to run faster than $O(mn)$, but you can test for equality among the entire set faster.

Improve this answer
$\endgroup$
0
$\begingroup$

Can't be done. If you compare $A$ and $B$ (both $m \times n$), if you compare less than $m \cdot n$ elements, the matrices can differ in the elements not compared. If you want to compare $A$ to a set of $r$ $B$ matrices, you'll have to compare against all of them, i.r. $m \cdot n \cdot r$ comparisons. Maybe some smart preprocessing of the $B$ matrices can cut down the factor $r$ for the comparison of $A$ to the set of $B$s, but doing that won't be cheap. If you suspect most of the time they aren't equal, a fingerprint (i.e., a hash like SHA265) of the elements of the $B$ will tell you cheaply which ones can't be equal to $A$, but you'll have to check for equality.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.