Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a matrix:

$$ A_{m,n} = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{pmatrix} $$

$a_{i,j}$ is a signless integral and bounded. And $b_{i,j}$ is the same. Is there any similarity function between $a_{i,j}$ and $b_{i,j}$. Such that $f(a_{i,j})=f(b_{i,j})$ if and only if $a_{i,j}=b_{i,j}$.

For example, the rank of matrices can identify a class of matrices, not a single matrix.

share|improve this question
    
What exactly do you mean by "identity" here? One can see a complex in different ways, e.g. a matrix can be both symmetric and orthogonal, or Hessenberg and banded, or any number of other properties... –  J. M. Feb 14 '12 at 3:46
    
I don't understand. On the simplest interpretation of your question, the way to detect the identity is to see whether $AB=BA=B$ for all matrices $B$. –  Gerry Myerson Feb 14 '12 at 3:47
1  
I think by "identity" the OP means "how can I tell if some matrix is identical to a given matrix $A$?" I don't really understand what kind of answer the OP is expecting other than "compare their entries." –  Qiaochu Yuan Feb 14 '12 at 3:54
1  
If "$a_{i,j}$ is a signless integral and bounded" means the entries are nonnegative integers with some known bound $B$, then $f(M) = \sum_i \sum_j a_{i,j} B^{i+mj}$ would do. This could conveniently be written as $f(M) = u^T M v$ where $u^T = [B, B^2, \ldots, B^m]$ and $v = [B^m, B^{2m}, \ldots, B^{nm}]^T$. –  Robert Israel Feb 14 '12 at 9:13
1  
Following Robert, maybe hashing is really what you are looking for: en.wikipedia.org/wiki/Hash_function ? –  Hauke Strasdat Feb 14 '12 at 11:16

1 Answer 1

In the absence of additional assumptions about the matrix (such as: symmetric, triangular, orthogonal, etc), the matrix form does not really help. The problem is exactly the same as for the list of $mn$ integer values. If each of these integers takes $k$ bits to store, the similarity function $f$ could be their concatenation into a string of $mnk$ bits. This is essentially the function given by Robert Israel: $f(M)=\sum_{ij} a_{ij}B^{i+mj}$ where $B$ is an upper bound on the entries of $M$.

If more is known about the matrix, then some compression is possible: for example, a square antisymmetric matrix of size $n$ is determined by its $n(n-1)/2$ entries lying above the main diagonal.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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