Emil Marinov

Author: emarinov

  • 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.

  • p->q Norm

    p → q Norm

    The $p \rightarrow q$ norm of a matrix comes up in approximation algorithms, small set expansion, and analysis. It measures the most that the $q$-norm can be larger than the $p$-norm, effectively prioritizing concentrated vectors. The norm of a matrix can be thought of as “how much it blows up an input vector”.

    $$ \|A\|_{p \rightarrow q} = \sup_{x \neq 0} \frac{\|Ax\|_q}{\|x\|_p} $$

    When solving for this, note that there are two ways in which to take the norm:
    1) sum norm, and
    2) expectation norm.

    Sum Norm

    $$ \|x\|_p = \left(\sum_i |x_i|^p \right)^{\frac{1}{p}} $$

    Expectation Norm

    $$ \|x\|_p = \mathbb{E}_i \left(|x_i|^p\right)^{\frac{1}{p}} $$

    Note that as $p$ is increased, it weights more strongly the heavy elements of the vector. This is why $\|\cdot\|_{\infty}$ is simply the largest vector element.

    Example 1

    Solve for:

    $$ \|\mathbb{I}\|_{2 \rightarrow 4} $$

    $$ \|\mathbb{I}\|_{2 \rightarrow 4} = \sup_{x \neq 0} \frac{\|\mathbb{I}x\|_4}{\|x\|_2} $$

    Let’s contrast the behavior of the $2 \rightarrow 4$ norm using two input vectors, $x_1$ and $x_2$.

    $$ x_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$

    $$ \|\mathbb{I}\|_{2 \rightarrow 4} = \frac{\left[\frac{1}{n}(1^4 + 0 + 0 + 0)\right]^{\frac{1}{4}}}{\left[\frac{1}{n}(1^2 + 0 + 0 + 0)\right]^{\frac{1}{2}}} = \frac{n^{-\frac{1}{4}}}{n^{-\frac{1}{2}}} = n^{\frac{1}{4}} $$

    $$ x_2 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} $$

    $$ \|\mathbb{I}\|_{2 \rightarrow 4} = \frac{\left[\frac{1}{n}(1^4 + 1^4 + 1^4 + 1^4)\right]^{\frac{1}{4}}}{\left[\frac{1}{n}(1^2 + 1^2 + 1^2 + 1^2)\right]^{\frac{1}{2}}} = 1 $$

    It is apparent that the 4-norm is highest when vectors are concentrated. Note that the above results are opposite when using the sum norm.

    Important Result: If the matrix in question preserves the 2-norm, such as a unitary matrix, the most the $2 \rightarrow 4$ norm can be is larger by a factor of $n^{\frac{1}{4}}$.

    The $2 \rightarrow 2$ norm of a graph’s normalized adjacency matrix (“normalized” means it’s a random walk matrix) is always 1. But, the second largest eigenvalue indicates expansion of the graph, as it provides information about the rate at which a random walk mixes; if something is orthogonal to the stationary distribution, how quickly will that vector decay under mixing on the graph.

    If the $2 \rightarrow 4$ norm is applied to the adjacency matrix of a graph, it is similar to the $2 \rightarrow 2$ norm, except that the 4 favors small sets, telling more about small set expansion.

    Theorem 1

    If $A$ is the normalized adjacency matrix of a graph and $P_{\ge \lambda}$ is the projector onto the $\ge \lambda$ eigenspace, then the graph has very good small set expansion. All sets of size $\delta$ expand greatly iff the projector has a small $2 \rightarrow 4$ norm:

    $$ \Phi_\delta \ge 1 – \lambda^{O(1)} \iff \|P_\lambda\|_{2 \rightarrow 4} \le \frac{1}{\delta^{O(1)}} $$

    Solving $2 \rightarrow 4$ norm

    Recognize that

    $$ \|Ax\|_4 = \left(\mathbb{E}_i |\langle a_i, x \rangle|^4\right)^{\frac{1}{4}} = \left(\frac{1}{m} \sum_{i=1}^m \langle a_i, x \rangle^4 \right)^{\frac{1}{4}}. $$

    Now, normalize $x$: $x’ = \frac{x}{\|x\|_2}$.

    $$ \sup_{x \neq 0} \frac{\|Ax\|_4}{\|x\|_2} = \left[\max_{\|x\|_2 = 1} \mathbb{E}_i |\langle a_i, x \rangle|^4\right]^{\frac{1}{4}} $$

    $$ \therefore \|A\|_{2 \rightarrow 4}^4 = \max_{\|x\|_2=1} \mathbb{E}_i \langle a_i, x \rangle^4 $$

    The RHS can be thought of as a homogeneous degree-4 polynomial in the entries of $x$ constrained by the $l_2$ unit sphere. Optimizing a problem over the unit sphere is a non-convex problem and generally hard. This is where something like the Lasserre hierarchy comes in.

    Multilinear algebra provides the following equation:

    $$ \langle a_i, x \rangle^4 = (a_i^T x)^4 = \langle a_i^{\otimes 4}, x^{\otimes 4} \rangle $$

    Also, bilinearity allows bringing the expected value inside the inner product. Thus:

    $$ \max_{\|x\|_2=1} \mathbb{E}_i \langle a_i, x \rangle^4 = \max_{\|x\|_2=1} \langle \mathbb{E}_i a_i^{\otimes 4}, x^{\otimes 4} \rangle $$

    This allows us to separate into something that depends on the problem and something that we are to maximize over. Now in taking the convex hull, we can separate it into something that’s instance-dependent and something that’s universal.

    Aside — Observables

    An observable is a Hermitian matrix, $M$, with expectation value $x^\dagger M x$. Because the trace of a scalar is the scalar:

    $$ x^\dagger M x = \mathrm{Tr}(x^\dagger M x) $$

    Because trace holds the cyclic property:

    $$ \mathrm{Tr}(x^\dagger M x) = \mathrm{Tr}(M x x^\dagger) $$

    From the Frobenius inner product:

    $$ \mathrm{Tr}(M x x^\dagger) = \langle M^\dagger, x x^\dagger \rangle $$

    Because $M$ is Hermitian, $M = M^\dagger$:

    $$ x^\dagger M x = \langle M, x x^\dagger \rangle $$

    By writing it like this, we have separated the quantity we are measuring versus the state we are measuring. Thus, the quantities that we measure are linear in the state, like in probability theory:

    $$ \mathrm{Tr}(M \rho) = \lambda \mathrm{Tr}(M \rho_1) + (1 – \lambda) \mathrm{Tr}(M \rho_2) \quad \text{if} \quad \rho = \lambda \rho_1 + (1 – \lambda) \rho_2. $$

    Aside — Density Matrices

    Density matrices can represent mixed states, and the set of density matrices can be thought of as a convex hull:

    $$ D(n) = \mathrm{conv}\{x x^\dagger \mid \|x\|_2 = 1\} $$

    Why is this true?

    A density matrix \(\rho \in \mathbb{C}^{2n \times 2n}\) satisfies:

    1. \(\rho \succeq 0\)
    2. \(\mathrm{Tr}(\rho) = 1\)

    A convex combination of pure states looks like:

    $$ \rho = \sum_i \lambda_i x_i x_i^\dagger $$

    where \(\lambda_i \ge 0\) and \(\sum_i \lambda_i = 1\).

    This is a statistical mixture of pure states \(x_i\) each with probability \(\lambda_i\). Mathematically, this is what it means to be in the convex hull of pure state projectors. The Krein–Milman theorem in convex analysis tells us that any compact convex set is the convex hull of its extreme points. Thus, every mixed state is a convex combination of pure states.

    Because density matrices combine quantum mechanics and probability, it allows us to distinguish quantum entanglement from classical correlation. For a pure state, if you’re correlated then you’re entangled. In determining correlation versus entanglement for, say, two particles, then you define the separable states to mean unentangled, and those are all convex combinations of product states; all the classically correlated states.

    $$ \mathrm{sep}(n,n) = \mathrm{conv}\{x x^\dagger \otimes y y^\dagger \mid \|x\|_2=1, \|y\|_2=1\} $$

    Note that a density matrix of rank-1 corresponds to a pure state.

    Because the above are a convex set, we can define the support function as the maximum inner product of anything in the set given an input \(M\). For example, someone tells you they’re going to make a measurement, \(M\). Prepare for me a quantum system \(\rho\) that maximizes this value. The hardness result for this problem is:

    $$ 3\mathrm{SAT}[\log^2(n)] \le_p h_{\mathrm{sep}}(M) = 1 \quad \text{or} \quad h_{\mathrm{sep}}(M) \le \frac{1}{2} $$

    for some \(M\) satisfying \(0 \le M \le \mathbb{I}\) and \(M\) of size \(n^2 \times n^2\). Assuming the exponential time hypothesis, this implies a lower bound of \(\Omega(n^{\log n})\) [3].

    $$ h_{\mathrm{sep}}(M) = \max\{ \langle M, \rho \rangle \mid \rho \in \mathrm{sep} \} $$

    We can also define the weak membership problem (WMEM): Given \(\rho \in \mathrm{sep}\) or \(\mathrm{dist}(\rho, \mathrm{sep}) > \epsilon\), determine which? Essentially, after you’ve determined every entry in the matrix \(\rho\), have you made something separable or something that is far from separable? Even though a price that’s exponential in the number of qubits to solve for every entry in the density matrix has been incurred, this problem may still be unsolvable.

    Because this problem is a convex set, the two problems above are roughly equivalent in difficulty.

    Monogamy of Entanglement

    $$ \rho^{ABC} = \mathbb{C}^{n^3 \times n^3} $$

    This density matrix composed of three subsystems can be analogous to a probability distribution that has marginal probabilities between subsections of the system, like \(AB\) or \(AC\). For example:

    $$ \rho^{AB} = (\mathrm{id}^A \otimes \mathrm{id}^B \otimes \mathrm{Tr}^C)(\rho^{ABC}) $$

    Facts

    • When \(p=\infty\) and \(q=1\), it is the Grothendieck problem, of which MAXCUT is a special case [1].

    References

    1. Estimating the Matrix \(p \rightarrow q\) Norm. https://math.mit.edu/~urschel/preprints/norm.pdf
    2. Unique games, the Lasserre hierarchy and monogamy of entanglement. Harrow, Aram. https://www.youtube.com/watch?v=cM7GuAzkFRU
    3. Testing product states, quantum Merlin-Arthur games and tensor optimisation. Aram W. Harrow, Ashley Montanaro. https://arxiv.org/abs/1001.0017
    4. Hypercontractivity, Sum-of-Squares Proofs, and their Applications. https://arxiv.org/pdf/1205.4484
    5. Quantum de Finetti Theorems under Local Measurements with Applications. https://arxiv.org/pdf/1210.6367

  • 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$.