3

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}

jiazhen he
  • 31

1 Answers1

0

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) \}.$$

Alex Ravsky
  • 90,434