3
$\begingroup$

Given a matrix A, how to measure its similarity (row and column permutations can be performed on A) to triangular form, here the triangular form is like
\begin{align} M=\begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \end{align} This triangular form is different from upper triangular matrix. Besides requiring all the entries below the main diagonal are zero, I'd like the entries above the main diagonal are 1 as much as possible.

For example, the similarity between A,B,C and M should satisfy $sim(A,M)>sim(B,M)>sim(C,M)$

A has the highest similarity, which is actually same as M after swapping column 1 and 4.

\begin{align} A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} & B = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} & C = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \end{align}

$\endgroup$
  • $\begingroup$ What about some norm of $X-M$, where $X=A,B,C$? $\endgroup$ – Algebraic Pavel Jan 5 '15 at 11:48
0
$\begingroup$

If all elements of $A$ are supposed to be $0$ or $1$, then we can use an idea of Hamming distance. For this purpose let $\sigma(A)$ be the set of all matrices, which can be obtained from the matrix $A$ by row and column permutations. For each matrix $A’\in \sigma(A)$ let $d’(A’,M)$ be the number of cells of matrices $A’$ and $M$ at which the corresponding numbers are different. Finally, put $$d(A,M)=\min\{ d’(A’,M): A’\in \sigma(A) \}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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