5
$\begingroup$

Consider $\Omega = Mat_{n\times n}(\{0,1\})$ - space of matrices of $1$s and $0$s. We want to determine does there exist $A\in\Omega$ : $A^2 = J_n$, where $J_n$ is a matrix of ones. We suppose that there are standard arithmetical operations : ($\mathbb{R}$,+,$\cdot)$.

Actually I don't understand how to step it. I've thought about using some properties about spectrum of $J_n$, but it looks like failure moment.

$\endgroup$
11
  • 1
    $\begingroup$ uncertain about your notation. What are the elements of matrix $A$ permitted to be?? $\endgroup$ – Will Jagy Feb 20 '20 at 21:39
  • 1
    $\begingroup$ Are $0$ and $1$ here elements of $\Bbb Z$ or of $\Bbb Z_2$? (I'm not sure whether it makes a difference in whether the answer is positive.) $\endgroup$ – Travis Willse Feb 20 '20 at 21:47
  • 1
    $\begingroup$ @DonaldSplutterwit added $\endgroup$ – openspace Feb 20 '20 at 21:50
  • 3
    $\begingroup$ The trace of A would have to be $\sqrt{n}$... this immediately rules out an awful lot of cases of n $\endgroup$ – user8675309 Feb 20 '20 at 22:09
  • 1
    $\begingroup$ @user8675309 why should it be $\sqrt{n}$ ? $\endgroup$ – openspace Feb 20 '20 at 22:24
6
$\begingroup$

If $n$ is a square (such as 4 in the example below), then the following pattern seems to work $$ \begin{bmatrix} 1& 1& 0& 0 \\ 0& 0 & 1&1 \\ 1&1 &0 &0 \\ 0&0 &1 &1 \end{bmatrix} $$ + many row-column permutations.

$\endgroup$
4
  • $\begingroup$ Do you mean that each row has $\sqrt{n}$ $1$-s? $\endgroup$ – openspace Feb 20 '20 at 22:35
  • $\begingroup$ @openspace that seems to be necessary, but not sufficient. You cannot just change row 2 and 3 in my example $\endgroup$ – Peter Franek Feb 20 '20 at 22:36
  • $\begingroup$ Yes look's like for $n^2$ we have : matrix with this pattern give us $J_n$. But why only $n^2$? $\endgroup$ – openspace Feb 20 '20 at 22:36
  • $\begingroup$ This was explained in the comments -- or look here math.stackexchange.com/questions/506962/… $\endgroup$ – Peter Franek Feb 20 '20 at 22:38
7
$\begingroup$

Note that $spectrum(J_n)=\{0,\cdot,0,n\}$; consequently, $spectrum(A)=\{0,\cdots,0,\pm\sqrt{n}\}$ and, necessarily, $trace(A)=\sqrt{n}$. Thus, $A$ may exist only when $n$ is a square. In this last case, $A$ exists

For $n=1$, $A=[1]$.

For $n=4$,

enter image description here

For $n=9$,

enter image description here

and so on...

$\endgroup$
3
$\begingroup$

The answer is negative when $ n = 2 $. There, one finds by direct computation that the only matrices $ A $ which satisfy $ A^2 = J_2 $ are $ \pm \cfrac{\sqrt{2}}{2} J_2 $, which does not belong to the desired space.

$\endgroup$
0
$\begingroup$

Consider:

$(J_n)_{ij} = \sum_{k = 0}^{n} A_{ik} \cdot A_{kj}$

(By the way: Do(es a) row / column permutation(s) of $A$ change the result?)

Using the formula above and that the entries of $A$ are 0 or 1, it is clear that $(J_n)_{ii} = 1$ as requested if and only if there is (for every tuple $(i, j)$) exactly one k such that $a_{ik}$ and $a_{ki}$ = 1. How does $A$ then look like? Try now a proof by contradiction.

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