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?
3
-
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$– HenrikRüpingCommented 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$– Federico PoloniCommented May 28, 2019 at 9:16
-
1$\begingroup$ Where does probability enter into this? $\endgroup$– SomosCommented May 28, 2019 at 17:37
Add a comment
|