# Measure to compare matrix $A$ and permuted matrix $B$

I have a matrix $A$ and matrix $B$ of same dimension. We generally use $||A-B||_F^2$ (Forbenius norm) to compare these two matrix how close they are to each other. Here we assume the $col_i$ of matrix $A$ corresponds to $col_i$ of matrix $B$ and so on and hence the subtraction make sense. If the matrix $A$ and $B$ are equal we have the Forbenius norm as zero. When the matrix $A$ and $B$ deviates, the Forbenius norm increases.

But in my case $col_i$ of matrix $A$ may corresponds to $col_j$ of matrix $B$.
Is there any measure to compare these two matrices where the columns are permuted in one matrix?

One can say that, we can find all the permuted matrix $B$ and evaluate $||A -\operatorname{perm}(B)||_F^2$ and choose the best $B$. However, this its gets problematic when the number of columns increases (we need to evaluate for $n!$ permutation).

Is there any other measure (not necessarily Forbenius norm) to evaluate the closeness of matrix $A$ and $B$ where the correspondence is from $col_i$ of $A$ to $col_j$ of B

-

Define the cost of matching the $i$th column of $A$ (which I'll call $a_i$) with the $j$th column of $B$ (i.e. $b_j$) as $c(i,j) = \| a_i - b_i \|^2$. A permutation of the columns of $B$ can be viewed as a bijection $f\colon \{1,\ldots,n\}\to\{1,\ldots,n\}$ such that the $i$th column of the permuted matrix is $b_{f(i)}$. Then you want to minimize the norm $$\|A-\operatorname{perm}(B)\|^2_F = \sum_{i=1}^n\|a_i-b_{f(i)}\|^2 = \sum_{i=1}^n c(i,f(i)).$$ This is nothing but the assignment problem, which can be solved in polynomial time using, for example, the Hungarian algorithm.
From what I gather from your question, according to what you want, $m(A, B) = \min_{\sigma\in S_n}\|A - \sigma(B)\|_F^2$ is the best you can do, where $S_n$ is the group of permutations on $n$ letters and $\sigma(B)$ is a permutation of columns of $B$. Why? Because embedded in your problem is the following decision problem: given two $n\times m$ matrices $A$, $B$, decide whether $A = \sigma(B)$ for some $\sigma\in S_n$. Indeed, if $A = \sigma(B)$ for some $\sigma \in S_n$, then $m(A, B) = 0$; otherwise, $m(A, B)\neq 0$.