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
