Category: Proofs

  • Geometry of MAX-CUT


    The equivalence between an $nxn$ real matrix $M$ where $M_{ij} \sim N(0,1)$ and random points uniformly sampled from the unit sphere $S^{n-1}$ is an important result in probability theory, measure theory, geometry, and theoretical computer science.

    Let $g \sim N(0, I_n)$.  Show that $g/||g|| \sim U(S^{n-1})$.  Prove that choosing a random hyperplane through the origin is equivalent to drawing $r \sim N(0, I_n)$ and cutting according to the sign of the projection.

    Proof

    Let $\vec{u}, \vec{v} \in \mathbb{R}^n$ such that $|\vec{u}| = |\vec{v}| = 1$ be the set of $n$-dimensional unit vectors and let $G = O(n)$ be the orthogonal group action acting upon this set. For rotational invariance on $S^{n-1}$, an isometry must be shown such that $\vec{u} \cdot \vec{v} = o\vec{u} \cdot o\vec{v}$, where $o \in O(n)$.

    $(o\vec{u}) \cdot (o\vec{v}) = (o\vec{u})^T (o\vec{v}) = \vec{u}^T o^T o \vec{v} = \vec{u}^T \vec{v} = \vec{u} \cdot \vec{v}$

    Note that $o^T o = I$. Because the columns of $o \in O(n)$ are orthogonal, a transformation by $o$ yields an inner product-preserving isometry.

    Now, pick a random unit vector $\vec{u} \sim S^{n-1}$ and define the orthogonal hyperplane as $H_{\vec{u}} = \{ \vec{x} \in \mathbb{R}^n | \langle \vec{x}, \vec{u} \rangle = 0 \}$. The hyperplane may act as a partition barrier, where $sign(\langle \vec{v_i}, \vec{u} \rangle)$ partitions vectors $\vec{v_i}$.

    Let $\vec{r} \sim N(0, I)$ and let its polar decomposition be $\vec{r} = \rho \vec{w}$, where $\rho$ represents the length of the vector, $\rho = ||r|| \ge 0$ and $\vec{w}$ is the direction, $\vec{w} = r / ||r|| \in S^{n-1}$. Because of the invariance proved above, $w \sim U(S^{n-1})$, meaning it is independent of $\rho$.

    ${sign}(\langle \vec{v}_i, \vec{r} \rangle) = {sign}(\rho \langle \vec{v}_i, \vec{w} \rangle) = {sign}(\langle \vec{v}_i, \vec{w} \rangle)$

    In the case of ties, randomly pick a partition to assign to $v_i$. However, notice that ${Pr}(\langle v_i, r \rangle) = 0$, since Gaussians have a continuous distribution. (I originally wrote the preceding ‘.’ with a ‘!’ due to my excitement of this fact, but I changed it due to the factorial ambiguity.)

    Thus, it has been proved that choosing a random hyperplane through the origin is equivalent to drawing $r \sim N(0, I_n)$ and cutting according to the sign of the projection. $\square$

    Remarks

    Invariance on the unit $(n-1)$-sphere implies a lack of preference for any vector centered at the origin and pointing to the surface; applying any rotation or reflection to a Gaussian vector does not change its distribution. On a compact homogeneous space like $S^{n-1}$, the Haar measure is the only probability distribution that is invariant under all orthogonal transformations. Proof of this is a fun exercise involving left cosets and is left as an exercise to the reader.

    The proof above is a key part in the seminal Goemans-Williamson algorithm for MaxCut polynomial time approximation. The original scalar binary variable domain $D = \{-1, 1 \}$ is relaxed into unit vectors, $\vec{v}_i \in S^{n-1}$, where $||\vec{v}_i|| = 1$ and $n$ is the number of nodes on the constraint graph. These vectors form Gram matrices, $Y$, where $Y_{ij} = \vec{u}_i \cdot \vec{v}_j$ subject to the constraints $Y_{ii} = 1$ and $Y \succeq 0$. This is solvable as a semi-definite program, yielding Cholesky-decomposed vector solutions to the relaxation. A random hyperplane is selected from $S^{n-1}$, and these vectors are partitioned according to which side of the hyperplane the fall on.

  • M_2(R) Subring Isomorphic to Complex Numbers

    Chapter 7.3 – Exercise 13
    Abstract Algebra – Dummit and Foote
    Prove that the ring $M_2(\mathbb{R})$ contains a subring isomorphic to $\mathbb{C}$.

    Proof
    My first thought is to create two representatives of $M_2(\mathbb{R})$, their images $c_1 = \phi(u)$ and $c_2 = \phi(v)$, and see what they look like in the definition of a ring homomorphism.
    Let $u, v \in M_2(\mathbb{R})$ and let $c_1, c_2 \in \mathbb{C}$. For a ring homomorphism to exist, it must meet the additive condition $\phi(u+v) = \phi(u) + \phi(v)$ and the multiplicative condition $\phi(uv) = \phi(u)\phi(v)$. Let $u = \begin{bmatrix}a&b\\c&d\end{bmatrix}$, $v = \begin{bmatrix}\tilde{a}&\tilde{b}\\\tilde{c}&\tilde{d}\end{bmatrix}$, $c_1 = x + yi$, and $c_2 = \tilde{x} + \tilde{y}i$, where $x, y, \tilde{x}, \tilde{y} \in \mathbb{R}$.
    I started out by seeing if I could identify any structural similarities between $uv$ and $c_1 c_2$:
    $\phi(uv) = \phi\left(\begin{bmatrix}a\tilde{a}+b\tilde{c}&a\tilde{b}+b\tilde{d}\\c\tilde{a}+d\tilde{c}&c\tilde{b}+d\tilde{d}\end{bmatrix}\right) = \phi(u)\phi(v) = c_1 c_2 = x\tilde{x} + x\tilde{y}i + y\tilde{x}i – y\tilde{y}$
    Observing that there are four terms on the right hand side of the equation, I immediately thought of the trace operator, yielding four similar terms on the left.
    ${Tr}\left(\begin{bmatrix}a\tilde{a}+b\tilde{c}&a\tilde{b}+b\tilde{d}\\c\tilde{a}+d\tilde{c}&c\tilde{b}+d\tilde{d}\end{bmatrix}\right) = a\tilde{a} + b\tilde{c} + c\tilde{b} + d\tilde{d}$
    Verifying that the right hand side of the multiplicative homomorphism condition holds:
    ${Tr}\left(\begin{bmatrix}a&b\\c&d\end{bmatrix}\right){Tr}\left(\begin{bmatrix}\tilde{a}&\tilde{b}\\\tilde{c}&\tilde{d}\end{bmatrix}\right) = (a+d)(\tilde{a} + \tilde{d}) = a\tilde{a} + a\tilde{d} + d\tilde{a} + d\tilde{d}$
    I noticed the LHS and RHS would be equivalent if $a=b$, $c=d$, $\tilde{a} = \tilde{b}$, and $\tilde{c} = \tilde{d}$.
    ${Tr}\left(\begin{bmatrix}a\tilde{a}+a\tilde{d}&a\tilde{a}+a\tilde{d}\\d\tilde{a}+d\tilde{d}&d\tilde{a}+d\tilde{d}\end{bmatrix}\right) = {Tr}\left(\begin{bmatrix}a&a\\d&d\end{bmatrix}\right){Tr}\left(\begin{bmatrix}\tilde{a}&\tilde{a}\\\tilde{d}&\tilde{d}\end{bmatrix}\right) = a\tilde{a} + a\tilde{d} + d\tilde{a} + d\tilde{d}$
    If my reasoning up to this point is correct, then it would indicate the subring in question is the set of matrices $S = \{s \in M_2(\mathbb{R})\quad|\quad {rank}(s) = 1\}$.
    The challenge at this point is to relate the homomorphic multiplicative map on $M_2(\mathbb{R})$ to the multiplicative operation, which could be different than the multiplicative operation of the 2×2 real matrices, on the complex numbers. In other words, how is the following equality achieved?
    $a\tilde{a} + a\tilde{d} + d\tilde{a} + d\tilde{d} = x\tilde{x} + x\tilde{y}i + y\tilde{x}i – y\tilde{y}$
    Aside from trivially assigning $a=x$, $\tilde{a} = \tilde{x}$, $d=y$, and $\tilde{d} = \tilde{y}$, we see that there is an $i$ term associated with $a\tilde{d}$ and $d\tilde{a}$, and there is a negative, or $i^2$, in front of the $d\tilde{d}$. After a little bit of thought, I realized that the multiplicative operation on the RHS MUST be different than the one on the LHS, and it must introduce the imaginary term (on further thought, I see that the LHS must introduce the imaginary term as well; so that initial conclusion was wrong). To get the two sides equal above, each of the matrix terms being multiplied in the homomorphism must somehow introduce an $i$ to the bottom right $d$:
    ${Tr}\left(\begin{bmatrix}a&a\\d&d\end{bmatrix}\begin{bmatrix}1&0\\0&i\end{bmatrix}\right){Tr}\left(\begin{bmatrix}\tilde{a}&\tilde{a}\\\tilde{d}&\tilde{d}\end{bmatrix}\begin{bmatrix}1&0\\0&i\end{bmatrix}\right) = {Tr}\left(\begin{bmatrix}a&ai\\d&di\end{bmatrix}\right){Tr}\left(\begin{bmatrix}\tilde{a}&\tilde{a}i\\\tilde{d}&\tilde{d}i\end{bmatrix}\right) = (a+di)(\tilde{a} + \tilde{d}i) = a\tilde{a} + a\tilde{d}i + d\tilde{a}i – d\tilde{d}$
    We have found the multiplicative homomorphism! Let $c = \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}$ be the complex diagonal matrix from above. The homomorphism is the trace operator with matrix multiplication on the LHS and matrix multiplication with $c$ on the RHS:
    ${Tr}(ucvc) = {Tr}(uc){Tr}(vc)$
    Now, let’s verify that our homomorphism holds additively as well:
    ${Tr}\left(\begin{bmatrix}a & a \\ d & d\end{bmatrix}\begin{bmatrix}1&0\\0&i\end{bmatrix} + \begin{bmatrix}\tilde{a} & \tilde{a} \\ \tilde{d} & \tilde{d}\end{bmatrix}\begin{bmatrix}1&0\\0&i\end{bmatrix}\right) = {Tr}\left(\begin{bmatrix}a+\tilde{a} & (a+\tilde{a})i \\ d+\tilde{d} & (d+\tilde{d})i \end{bmatrix} \right) = {Tr}\left(\begin{bmatrix}a & a \\ d & d\end{bmatrix}\begin{bmatrix}1&0\\0&i\end{bmatrix}\right) + {Tr}\left(\begin{bmatrix}\tilde{a} & \tilde{a} \\ \tilde{d} & \tilde{d}\end{bmatrix}\begin{bmatrix}1&0\\0&i\end{bmatrix}\right) = a+\tilde{a}+(d+\tilde{d})i$
    This is exactly what one would expect adding two complex numbers together:
    $c_1 + c_2 = (x+iy) + (\tilde{x}+i\tilde{y}) = x+\tilde{x}+i(y+\tilde{y})$
    To finish the proof, the first two items indicating the homomorphism $\phi$ is an isomorphism and the last three items indicating that $S$ is a subring of $M_2(\mathbb{R})$ must be shown:
    • $\phi$ is additively injective
    • $\phi$ is additively surjective
    • $\phi$ is multiplicatively injective
    • $\phi$ is multiplicatively surjective
    • $S$ is not empty
    • $S$ is closed under subtraction
    • $S$ is closed under multiplication

    To show additive injectivity, let $m = \{M_2(\mathbb{R})\quad | \quad {rank}(m)=1\}$, let $u, v\in m$, and assume $u \neq v$ and that the homomorphism is not injective, or that $(\phi(uc) = \phi(vc)) \not\implies (u=v)$. Let $u = \begin{bmatrix}a & a\\d&d\end{bmatrix}$, $v = \begin{bmatrix}\tilde{a} & \tilde{a}\\\tilde{d}&\tilde{d}\end{bmatrix}$, and $c = \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}$.
    ${Tr}(uc) = {Tr}\left(\begin{bmatrix}a&ai\\d&di\end{bmatrix}\right) = a+di$
    ${Tr}(vc) = {Tr}\left(\begin{bmatrix}\tilde{a}&\tilde{a}i\\\tilde{d}&\tilde{d}i\end{bmatrix}\right) = \tilde{a} + \tilde{d}i$
    The pullback of the trace on a rank-1 2×2 matrix can only map to one value. Thus, $a=\tilde{a}$, $d=\tilde{d}$, and $u=v$. This is a contradiction of the initial assumption that $(\phi(uc) = \phi(vc)) \not\implies (u=v)$, as $(\phi(uc) = \phi(vc)) \implies (u=v)$. Another way to show this is to set $\phi(uc) = \phi(vc)$. Then, by the linearity of the additive homomorphism, $c\phi(u-v) = 0$, implying $u=v$. Thus, additive injectivity has been shown.

    To show additive surjectivity, it must be demonstrated that $a+di$ may be mapped onto $\forall a,d$. This is fairly trivial from observation, as the subring $S$ contains all 2×2 matrices that are rank-1.

    To show multiplicative injectivity, it must be shown that $(\phi(uc)=\phi(vc)) \implies (u=v)$. The same method for proving additive injectivity holds here, and the fact that a homomorphism is injective iff it has a trivial kernel falls from both of these demonstrations.

    To show multiplicative surjectivity, it must be shown that every complex number may be mapped onto via the homomorphism. This is similar to the additive case. For every complex number $x+yi$, there exists some rank-1 real 2×2 matrix $\begin{bmatrix}x & x\\y &y\end{bmatrix}$ that when scaled with $c$ tracially maps to it.

    To show the subring $S$ is not empty, it is obvious from observation. The subring $S$ contains an uncountably infinite amount of matrices, where $a$ and $d$ may be any real number.

    Next, it must be shown that $S$ is closed under subtraction:
    $\begin{bmatrix}a&a\\d&d\end{bmatrix}-\begin{bmatrix}\tilde{a}&\tilde{a}\\\tilde{d}&\tilde{d}\end{bmatrix} = \begin{bmatrix}a-\tilde{a}&a-\tilde{a}\\d-\tilde{d}&d-\tilde{d}\end{bmatrix}$
    This yields another real-valued 2×2 matrix of rank-1. Therefore, it is closed under subtraction.

    Finally, it must be shown that $S$ is closed under multiplication:
    $\begin{bmatrix}a&a\\d&d\end{bmatrix}\begin{bmatrix}\tilde{a}&\tilde{a}\\\tilde{d}&\tilde{d}\end{bmatrix} =\begin{bmatrix}a\tilde{a} + a\tilde{d} & a\tilde{a} + a\tilde{d}\\d\tilde{a}+d\tilde{d} & d\tilde{a}+d\tilde{d} \end{bmatrix}$
    $S$ has been shown to be closed under multiplication as well.

    Thus, it has been proved that $M_2(\mathbb{R})\cong \mathbb{C} \quad \square$.