# Squares of random binary matrices

Are there results/techniques pertaining to the analysis of squares of random matrices ?

More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with equal probability. Now if we want to analyze for any $u,v \in \{-1,1\}^n$, we can make a case for concentration of the value of $u^TAv$ using chernoff bound arguements. However suppose now we want to analyze the value of $u^TA^2v$. This time due to a lot of dependencies among the variables a chernoff type arguement becomes difficult or at least I cannot see it straightaway. Could someone point me to an analysis for this scenario ?

• While this is not an answer, it seems that powers of such an A will become "more and more Gaussian": maybe this might yield a back of the envelope estimate for the behavior ? Jun 15 '13 at 4:24
• Yes, thats what my guess is and I have been trying to formalize it exactly but havent got much progress yet .. was just wondering if there is already work on it
– NAg
Jun 15 '13 at 17:11
• There is the notion of subgaussian tails that is sufficient to prove a number of tail bounds on variables of this kind. It might be that you can show that the variables in A^2 have this property. See for example this paper by Matousek: dl.acm.org/citation.cfm?id=1400129 Jun 15 '13 at 17:30
• Thanks a lot for the links. Yes we would get that each entry in A^2 has a sub-gaussian tail, however I am not yet sure as to how to avoid the problem of dependence between these entries when we take their sum when computing uA^2v. The paper referred above does give a sub-gaussian behaviour result for sums of independent sub-gaussian variables. I am not sure how to avoid the dependence issues that arise here.
– NAg
Jun 15 '13 at 22:50
• again, I'm just wildly speculating, but maybe the dependency can be controlled and you can use a "weak dependence" chernoff bound (of which there are a few flavors) Jun 16 '13 at 6:12