1
$\begingroup$

Suppose I have two matrices $A, B \in \mathbb{R}^{n \times n}$. Assume that there is a way to change the signs of rows and columns of $A$ such that the resulting matrix is equal to $B$. In other words, assume that there exist diagonal matrices $D_1, D_2 \in \mathbb{R}^{n \times n}$ such that:

$$D_1AD_2 = B$$

where the diagonal entries of $D_1$ and $D_2$ are $\pm 1$.

Then is there an (efficient) algorithm to determine which rows and columns of $A$ changed sign to equal $B$?

Perhaps, some information could be retrieved from the entry-wise product of the $\pm 1$-sign matrix of $A$ and $B$, though I am not sure where to go from there.

$\endgroup$

1 Answer 1

1
$\begingroup$

Here's an approach that works if $A,B$ have no zero entries. Let $M$ denote the matrix whose entries satisfy $$ m_{ij} = \begin{cases} 1 & \operatorname{sgn}(A_{ij}) = \operatorname{sgn}(B_{ij})\\ -1 & \operatorname{sgn}(A_{ij}) \neq \operatorname{sgn}(B_{ij}) \end{cases} $$ where sgn denotes the sign (AKA signum) function. Note that $$ D_1AD_2 = A \odot D_1(ee^T)D_2 $$ where $\odot$ denotes the Hadamard product and $e = (1,\dots,1)^T$. With that, we see that we're looking for matrices $D_1,D_2$ such that $D_1(ee^T)D_2 = M$.

We are given that such matrices $D_1,D_2$ exist, which means that $M$ is necessarily of rank $1$. It follows that $M$ can be written in the form $uv^T$. Because all entries of $M$ are equal to $\pm 1$, we can take $u,v$ to be matrices whose entries are $1$ or $-1$.

From there, we see that $u = \operatorname{diag}(u)$ and $v = \operatorname{diag}(v)$, which means that we can simply take $D_1 = \operatorname{diag}(u)$ and $D_2 = \operatorname{diag}(v)$.

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