Given two secret square matrices, say $\left( {\begin{array}{*{20}{c}} {{a_{11}}}&{{a_{12}}}&{{a_{13}}}\\ {{a_{21}}}&{{a_{22}}}&{{a_{23}}}\\ {{a_{31}}}&{{a_{32}}}&{{a_{33}}} \end{array}} \right)$ and its transpose $\left( {\begin{array}{*{20}{c}} {{a_{11}}}&{{a_{21}}}&{{a_{31}}}\\ {{a_{12}}}&{{a_{22}}}&{{a_{32}}}\\ {{a_{13}}}&{{a_{23}}}&{{a_{33}}} \end{array}} \right)$, suppose the summations of the column vectors of both matrices, i.e.,$\sum\limits_{i = 1}^3 {{a_{ij}}} ,j \in \left[ {1,3} \right]$ and $\sum\limits_{j = 1}^3 {{a_{ij}}} ,i \in \left[ {1,3} \right]$ are public. I wonder whether there exists an algorithm, which is allowed to query a constant (i.e., independent of the dimension of the square matrix) number of positions in both matrices, such that it can determine whether these two secret matrices are transpose to each other with non-neglibile probability?

  • 2
    $\begingroup$ no. just restrict yourself to permutation matrices. Suppose you are allowed to query k positions in the matrix and k is less than the dimension n of the matrix. Then the question becomes how many permutation matrices are there with those k fixed entries. If there is at least one, you can get much more py postcomposing with a permutation that does not affect the k entries. $\endgroup$ May 28, 2019 at 9:08
  • 3
    $\begingroup$ You can see why this is impossible also with an easy degrees-of-freedom argument: you cannot determine a matrix in $\mathbb{R}^{n^2}$ for all $n$ given $2n+C$ linear conditions. $\endgroup$ May 28, 2019 at 9:16
  • 1
    $\begingroup$ Where does probability enter into this? $\endgroup$
    – Somos
    May 28, 2019 at 17:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.