Consider a set of all possible Binary rectangular matrices.
How many non-equivalent metrics can be defined? How to define non equivalent metrics on this set precisely?
Asked
Active
Viewed 121 times
2
-
The coefficients of your matrix are in $\Bbb K=\Bbb Z/2\Bbb Z$ hence there in $\Bbb K^{n\times m}$ there is $\min(n,m)+1$ matrix. – Hamou Aug 19 '14 at 15:55
-
Could you be little more clear? – Fukuzita Aug 19 '14 at 15:56
-
Two matrices $A,B$ are not equivalent iff $\text{rank}(A)\neq \text{rank}(B)$. – Hamou Aug 19 '14 at 16:07
-
By metric do you mean a distance function that gives this (finite??) set a metric topology? Did you mean to create a topology on all sizes of binary matrices taken together? – hardmath Aug 19 '14 at 16:37
-
Yes, I mean distance function by saying Metric. I want all possible non equivalent metrics on the set of matrices as mentioned. – Fukuzita Aug 19 '14 at 16:40
-
@SkSarifHassan: Important clarification -- all binary matrices of all sizes, or just binary matrices of fixed size $m\times n$ ? – hardmath Aug 19 '14 at 18:12
-
1All binary matrices of size fixed size m times n. – Fukuzita Aug 19 '14 at 23:46
-
Closely related, but arguably not quite a duplicate: Is it true that any metric on a finite set is the discrete metric?. – hardmath Aug 20 '14 at 03:33
1 Answers
2
If the space consists of binary $m\times n$ matrices for fixed integers $m,n \gt 0$, then the number of such matrices is finite. Any finite metric space has a discrete topology, so there is only one metric topology up to topological equivalence.
Indeed strong equivalence of metrics must also hold in this finite setting. Let $d_1(x,y)$ and $d_2(x,y)$ be two metrics on a finite set $S$. Let $e_1,e_2$ be the minimum distances $d_1(x,y)$, resp. $d_2(x,y)$, over all distinct $x,y \in S$. Similarly let $f_1,f_2$ be the maximum distances $d_1(x,y)$, resp. $d_2(x,y)$, over all distinct $x,y \in S$. Then for any distinct $x,y \in S$:
$$ d_1(x,y) \lt (f_1 + 1) = e_2^{-1} (f_1 + 1) e_2 \le e_2^{-1} (f_1 + 1) d_2(x,y) $$
and by a similar estimate, $d_2(x,y) \lt e_1^{-1} (f_2 + 1) d_1(x,y)$. Thus the two metrics are strongly equivalent.
hardmath
- 37,015
-
@ Hardmath, any reference? Can you precisely mention a metric? I can think about Hamming metric (number of mismatches matrix entriwise). How does this metric unique then in terms of strong equivalence of metrics? – Fukuzita Aug 20 '14 at 02:13
-
The reason I asked for a number of clarifications about your Question was to make sure the terms you were using ("metrics") were well-defined. You agree that by metric was meant a distance function. There is a widely adopted notion of equivalence of metrics which says two metrics are equivalent iff the topologies they give are the same (see link in Answer). – hardmath Aug 20 '14 at 03:08
-
By strong equivalence of metrics is meant that for two distance functions $d_1(x,y)$ and $d_2(x,y)$ there exist positive constants $c_1,c_2$ such that for all $x\neq y$: $$ d_1(x,y) \lt c_1 d_2(x,y); \text{ and } ; d_2(x,y) \lt c_2 d_1(x,y) $$ – hardmath Aug 20 '14 at 03:10
-
Thanks. So as I understood, there is unique non-equivalent metric on the set. – Fukuzita Aug 20 '14 at 04:21
-
Yes, and this depends only on the set being finite, not the particular set being binary matrices of a fixed size. – hardmath Aug 20 '14 at 04:27