I have a vector space with vectors whose components can take only integer values. I also have a symmetric square binary matrix A that can act on these vectors. I am interested in finding all vectors ${\bf x}$ whose components lie in the set $\{-1, 0, 1\}$ and such that the signs of all the components of the vector ${\bf y=Ax}$ are same as the signs of the corresponding components of the vector ${\bf x}$. I initially thought that these vectors would like in the subspace spanned by the eigenvectors of ${\bf A}$ with positive eigenvalues. But that doesn't seem to be correct to me now. Is there any way to find out these vectors?

Edit: After thinking over the comments, I think I did not ask the question correctly. So here it goes. I am working in a special basis with the basis vectors given as $(1, 0, 0,\cdots, 0), (0, 1, 0, \cdots, 0), \cdots, (0, 0, \cdots, 0, 1)$. In this basis, I am demanding that the components of my vectors must be integers and they, in general, won't be so in a different basis. Now, I want those vectors for which the components don't change signs in this basis.

  • 2
    $\begingroup$ A detail: if the component can only be integer than your vector space is not a vector space, but a $\mathbb Z$-module. I don't think that this can substantially help you, though. $\endgroup$ Dec 15 '17 at 15:25
  • 1
    $\begingroup$ The eigenvectors and values are independent of the basis but the sign changes induced by the transformation depend on which basis you've chosen. Any method used to find such values should be done relative to the basis given to account for this. $\endgroup$ Dec 15 '17 at 15:56
  • $\begingroup$ Are you looking for a fast algorithm to compute these vectors or some theoretical insight? $\endgroup$
    – Hyperplane
    Dec 15 '17 at 16:17
  • $\begingroup$ What are the scalars? Where does $A$ live? The problem is a little underspecified as is. $\endgroup$
    – dbx
    Dec 16 '17 at 0:04
  • $\begingroup$ I have added some corrections now. Thanks for pointing those out. $\endgroup$
    – Peaceful
    Dec 17 '17 at 6:42

Maybe this answer is tautological or I did not understand the question correctly but here it goes: So $A \in \{0,1\}^{n\times n}$ and $x \in \{ -1,0,1\}^n$ and it should hold for all $i \in \{1,\dots,n\}$ that $$ \text{sgn}((Ax)_i) = x_i. $$

This is the case if for all $i$ where $x_i \neq 0$ if $$ \lvert \{j: a_{ij} = 1 \land x_j = x_i \} \rvert > \lvert \{j: a_{ij} = 1 \land x_j = - x_i \} \rvert $$ and for all $i$ where $x_i = 0$ if $$ \lvert \{j: a_{ij} = 1 \land x_j = -1 \} \rvert = \lvert \{j: a_{ij} = 1 \land x_j = +1 \} \rvert. $$

This is easy to see. Consider the the case $x_i \neq 0$, then $$ (Ax)_i = \sum_j a_{ij}x_j = \sum_{\{j:a_{ij} = 1 \land x_j = x_i\} } a_{ij}x_j + \sum_{\{j:a_{ij} = 1 \land x_j = - x_i\} } a_{ij}x_j \\ = \sum_{\{j:a_{ij} = 1 \land x_j = x_i\} } x_i + \sum_{\{j:a_{ij} = 1 \land x_j = - x_i\} } -x_i. $$ The case $x_i = 0$ can be checked in the same way.


I can provide you just a starting hint.

Consider the 2D case.

All the possible vectors $\bf x$ will thus lay on the axes ($(1,0)$, etc.) and on the diagonals ($(1,1)$, etc.) of a square of side $2$ centered at the origin.
For our purpose, we can also consider the corresponding points, obtained by moving the original ones along the ray from the origin, until bringing them on the unit circle ($(0,1),\, (\sqrt{2}/2,\sqrt{2}/2),\cdots$), i.e placed at multiples of $\pi /4$.

Now the action of any matrix on the set of points on the circle will consist, by the SVD decomposition, into a rotation, a stretch and a further rotation, with the final result that they will lay on an ellipse.

If the matrix is diagonal, its action will be a stretch, and all the points will preserve the sign of each of their coordinates.

If the matrix is just a rotation, the coordinates with a null value will loose their sign, while the others will preserve it if the angle of rotation is less than $\pi/4$ in absolute value.

So we can pass from SVD to the Polar decomposition and consider only the rotation given by the unitary component.

The fact that the matrices you are considering be binary seems to me not to simplify the process.
And passing to higher dimensions, to discern which components will preserve their sign under a rotation does look to be a complicated process in general.


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.