8

You have reduced the graph isomorphism problem to a 0-1 programming problem. 0-1 programming problems are NP-hard in general, so the question is whether your particular case is an exception. You haven't provided evidence for that. Many simple ideas work nicely for a few random examples, but when faced with carefully chosen hard examples they don't work. My ...


5

It's false. Take the subalgebra of $M_3(K)$ generated by the matrices $\begin{bmatrix} 0 & 0&0\\ 1 & 1 & 0\\ 0 & 0 & 1\end{bmatrix}$ and $\begin{bmatrix} 0 & 0 & 0\\ 0 &1&0\\ 1& 0&1\end{bmatrix}$. These two elements form a two element right zero semigroup and so the algebra they generate is just their span ...


5

Another suggestion: let $A_{2n}=M_{2n}-2I$ ($I$=identity matrix), so we are interested in $\ker A_{2n}$. Let $V$ be the vector space on which $A_{2n}$ acts, so we can regard $V$ as having a basis consisting of all subsets of $[2n]=\{1,2,\dots,2n\}$. Thus $V$ has a grading $V_0\oplus V_1\oplus\cdots \oplus V_{2n}$, where $V_i$ has a basis consisting of all $i$...


4

Only a suggestion: This smells of the Temperley-Lieb algebra. Eigenspaces of $M_n$ are invariant under the obvious action of the symmetric group $S_n$. The $2-$eigenspace of $M_n$ is thus a decomposition of irreps of $S_n$. The sum of squared dimensions for irreps with Young diagrams having at most $2$ rows of $S_n$ is the $n-$th Catalan number. The relation ...


4

The linear transformation converting $A$ into $B$ is sometimes called the "realignment map" (see https://arxiv.org/abs/quant-ph/0205017, for example): it is the linear transformation $R$ with the property that $R(\mathbf{e_i}\mathbf{e_j}^T \otimes \mathbf{e_k}\mathbf{e_\ell}^T) = \mathbf{e_i}\mathbf{e_k}^T \otimes \mathbf{e_j}\mathbf{e_\ell}^T$ for ...


4

It is a long standing open question if graph isomorphism can be solved in polynomial time when the input graphs are rigid. See here, for example. So, if correct, your algorithm would be a major breakthrough. I can't seem to follow the guessing step though.


4

Let $S$ b be the set of 3 x 3 matrices whose lower left 2 x 2 block equals zero. Then $S$ is an algebra satisfying the conditions, but containing no invertible matrix.


4

To attack this more theoretically: if A and B have a common eigenvector, then that must lie in $\ker Q$ and obviously $[Q,A]$ and $[Q,B]$ act trivially on this guy. Thus, we can take the perp to this eigenvector and ask the same question about the leftover matrices. Thus, we should assume that $A$ and $B$ have no common eigenvectors; in this case, you get ...


3

Let us first consider the case $D=I$. An invertible matrix $S$ can be (uniquely) factorized as $S=RQ$, where $R$ is upper triangular with positive diagonal entries and $Q$ is orthogonal, $QQ^\top=I$ (this is QR decomposition). Then $SS^\top = RQQ^\top R^\top = RR^\top$. On the other hand, by Cholesky decomposition, every positive definite symmetric matrix $A$...


3

Short answer from trying random matrix inputs: it is not true for $A = \begin{bmatrix}0.25634 & 0.417943& 0.696104 \\ 0.417943 & 0.0327021& 0.921007 \\ 0.696104 & 0.921007 & 0.0685762 \end{bmatrix}$ and $ B = \begin{bmatrix}1.64721 & 0.29856 & 0.455064 \\ 0.29856 & 0.448668 & 1.56321 \\ 0.455064 & 1....


2

The formula in @Carlo Beenakker answer does not give all rational orthogonal matrices, but only those for which $-1$ is not an eigenvalue. Here is a rational parametrization which gives all orthogonal matrices for $n=3$: $$\frac{1}{a^2+b^2+c^2+d^2}\left( \begin{array}{ccc}a^2+b^2-c^2-d^2 & 2bc-2ad & 2ac+2bd\\ 2ad+2bc & a^2-b^2+c^2-d^2 & 2cd-...


2

The one I put first was $$ \left( \begin{array}{rrr} 3 & -2 & -2 \\ -2 & 3 & -2 \\ -2 & -2 & 3 \\ \end{array} \right) $$ At the cost of possible non-integer value on the main diagonal, we may take real $w> 0$ in $$ \left( \begin{array}{rrrrr} w & -1 & -1 & -1 & -1 \\ -1 & w & -1 & -1 & -1 \\ -1 &...


1

I am not a real expert, but these problems can be absolute monsters for exact algorithms. I don't think you are doing anything wrong. Numerical irreducible decomposition might be a more feasible alternative; find yourself an expert in Bertini and try your problem with them.


1

This answer is really just an expansion of Mohan's and Zach Teitler's comments. I have only provided more detail, that's all. I don't care much for the points and if you want, just give the points to Mohan and Zach Teitler, but I thought it may be useful to the OP and to other readers to provide a complete answer. Let $\iota: Gr_2(\mathbb{C}^n) \to \mathbb{P}...


1

It may be too difficult to characterize all matrices that are products of pairwise averaging matrices, so it is probably a good idea to try to solve an easier problem (at least computationally) in a quotient monoid in order to obtain and compute many counterexamples. Let $[n]=\{1,\dots,n\}$. If $f\in S_{n}$, then let $\rho_{f}$ denote the permutation matrix $...


Only top voted, non community-wiki answers of a minimum length are eligible