Determining symmetricity of a matrix by multiplying with random vectors? Stemming from an approach in a hint/answer to this question here.
The idea is presented to determining wether a matrix is symmetric or not by measuring the following:
$$e = \|({\bf Av})^T - ({\bf v}^T{\bf A})\|$$
Where $\bf v$ is a column vector sampled from some suitable random distribution and $\bf A$ is a matrix.
Further we are assuming all scalars have "good" numerical precision, being real numbers represented with at least single precision floating point standard.
Assuming we know nothing about $\bf A$, which distribution should we sample from? And is there some way to estimate the probability that $e = 0$ if $\bf A$ is non-symmetric?
One argument was whether it will be a probabilistic approach or could be considered (for all practical purposes) to be a deterministic approach.
 A: Clearly, $e=0$ iff (P): for every $i$, $P_i(v)=\sum_{j\not= i}(a_{ij}-a_{ji})v_j=0$. Assume that the $(v_i)_i$ follow a normal law (for example) over $\mathbb{R}$. If $A$ is not symmetric, then there are $i_0,j_0$ s.t.  $a_{i_0j_0}\not= a_{j_0i_0}$. Then the polynomial $P_{i_0}(x)$ is not identically $0$. Thus the probability that $P_i(v)=0$ is $0$ and, consequently, the probability that (P) is satisfied is $0$. The previous reasoning requires an exact calculation.
However, it may happen that several $a_{ij}-a_{ji}$ are very small and $n$ is a great number. Anyway, the black box must calculate in the form $\sum_{j\not= i}(a_{ij}-a_{ji})v_j$ and not in the form $\sum_ja_{ij}v_j-\sum_j a_{ji}v_j$. Then, I think that we don't need many digits for the samples of the $(v_i)$; practically, some samples should be sufficient to conclude (it suffices to avoid the worst cases), at least, if $n$ is not a too great number .
EDIT. That I want to say: if we work with few significative digits, then the black box can give a result for $P_i(v)$ that is absolutely false; but, no matter, if the result is not zero, then the matrix is not symmetric !
