import marimo __generated_with = "0.11.5" app = marimo.App(width="medium") @app.cell(hide_code=True) def _(mo): mo.md( r""" # Generate random flat quantum permutation matrices # """ ) return @app.cell(hide_code=True) def _(mo): mo.md( r""" Let $A$ be a unital $C^*$-algebra. An $n \times n$ matrix $u = (u_{ij})_{1\le i,j\le n} \in \mathcal M_n(A)$ is called a **quantum permtuation matrix** if it satisfies the conditions below: 1. *Projection Entries:* Each entry is a projection: $$u_{ij}^2 = u_{ij} \quad \text{and} \quad u_{ij}^* = u_{ij} \quad \text{for all } i,j.$$ 2. *Row and Column Sums:* The entries in each row and each column sum to the unit of $A$: $$\sum_{j=1}^n u_{ij} = 1_A \quad \text{for all } i=1,\dots,n,$$ $$\sum_{i=1}^n u_{ij} = 1_A \quad \text{for all } j=1,\dots,n.$$ """ ) return @app.cell(hide_code=True) def _(mo): mo.md( """ We are interested here in the special case where: 1. the algebra $A$ is finite dimensional: $A = \mathcal M_d(\mathbb C)$ 2. the projections $u_{ij}$ have *unit rank* (we call $u$ *flat*); in particular $d=n$. """ ) return @app.cell def _(mo): mo.md( """ ## An alogrithm for generating random flat quantum permutation matrices ## """ ) return @app.cell def _(mo): mo.md( r""" We propose the following very simple algorithm for generating quantum permutation matrices, based on normalizing the rows and the columns of a matrix of unit rank projections. The alternating normalization of rows and columns is inspired by the **Sinkhorn algorithm** for producing random bistochastic matrices. 1. Start from a random matrix: $u_{ij}$ is the orthogonal projection on a random gaussian vector 2. While the error is larger than some predefined constant and the maximal number of steps has not been attained: 3. Normalize each row of $u$ 4. Normalize each column of $u$ 5. End-while 6. Output the matrix $u$ """ ) return @app.cell def _(mo): mo.md( r""" The row (respectively the column) normalization procedures are performed as follows. Collect all the vectors appearing on the $i$-th row of $u$ in a matrix $R_i$. Replace $R_i$ by $\tilde R_i$, the *closest unitary matrix* to $R_i$. This matrix can be obtained from the *singular value decomposition* of $R_i$: $$\text{ if } R_i = V_i \Delta_i W_i^*, \, \text{ then }\, \tilde R_i = V_i W_i^*.$$ """ ) return @app.cell def _(mo): mo.md( """ ## Implementation ## """ ) return @app.cell def _(mo): eps_slider = mo.ui.slider(0, 10, value=6) max_iter_slider = mo.ui.slider(1, 10000, value=2000) n_slider = mo.ui.slider(2, 20, step=1, value=4) return eps_slider, max_iter_slider, n_slider @app.cell def _(eps_slider, mo): mo.md(f"-lg(Error tolerance): {eps_slider} \t error_tolerance = 1e-{eps_slider.value}") return @app.cell def _(max_iter_slider, mo): mo.md(f"Max iterations: {max_iter_slider} \t max_iter = {max_iter_slider.value}") return @app.cell def _(mo, n_slider): mo.md(f"Matrix dimension: {n_slider} \t n = {n_slider.value}") return @app.cell def _(mo): button = mo.ui.run_button(label="Randomize!") button return (button,) @app.cell def _(errors, plt, scalar_products): # Create a figure with two subplots side by side fig, axs = plt.subplots(1, 2, figsize=(12, 5)) # Plot the errors on a log scale in the first subplot axs[0].semilogy(errors) axs[0].set_xlabel('Iteration') axs[0].set_ylabel('Error (log scale)') axs[0].set_title('Error Convergence') axs[0].grid(True) # Plot the histogram in the second subplot axs[1].hist(scalar_products, bins=30, edgecolor='black') axs[1].set_xlabel('Absolute Values Squared of Scalar Products') axs[1].set_ylabel('Frequency') axs[1].set_title('Histogram of Absolute Values Squared of Scalar Products') axs[1].grid(True) # Adjust layout to prevent overlap plt.tight_layout() plt.gca() return axs, fig @app.cell def _(mo): mo.md(r"""Note that for $n=2,3$ the histogram of scalar product shows only 0's and 1's: the vectors are either colinear or orthogonal. In other words, the elements $u_{ij}$ **commute**. For $n \geq 4$ this is no longer the case: the scalar product between vectors can take arbitrary values.""") return @app.cell def _(mo): mo.md( r""" ## Open questions ## 1. Prove the convergence of the algorithm for generic initializations. 2. Find the speed of convergence for arbitrary $n$ 3. What is the distribution of the scalar products for (large / given) $n$? How about the maximal norm of a commutator $[u_{ij}, u_{kl}]$? """ ) return @app.cell def _(mo): mo.md( r""" ## References ## 1. S. Wang, “Quantum symmetry groups of finite spaces,” _Communications in mathematical physics_, vol. 195, no. 1, pp. 195–211, 1998. 2. T. Banica, J. Bichon, and B. Collins, “Quantum permutation groups: a survey,” _Banach Center Publications_, vol. 78, no. 1, pp. 13–34, 2007. 3. T. Banica, I. Nechita, "Flat matrix models for quantum permutation groups," _Adv. Appl. Math._ 83, 24-46 (2017). """ ) return @app.cell def _(np): def generate_random_complex_gaussian_matrix(n): matrix = np.empty((n, n, n), dtype=np.complex128) for i in range(n): for j in range(n): real_part = np.random.normal(size=n) imag_part = np.random.normal(size=n) matrix[i, j] = (real_part + 1j * imag_part) / np.sqrt(2) return matrix def orthonormalize_vectors_svd(vectors): u, _, v = np.linalg.svd(vectors) return u @ v def error_QPM(u): err = -1; for i in range(u.shape[0]): slice = u[i, :, :] err = max(err, np.linalg.norm(slice @ slice.conj().T - np.eye(slice.shape[0]))) slice = u[:, i, :] err = max(err, np.linalg.norm(slice @ slice.conj().T - np.eye(slice.shape[0]))) return err def scalar_products_QPM(u): # Calculate the absolute values squared of the scalar products of the vectors in the matrix u scalar_products = [] for i in range(u.shape[0]): for j in range(1, u.shape[0]): for k in range(1, u.shape[0]): for l in range(1, u.shape[0]): scalar_product = np.abs(np.dot(u[i,j,:], u[k,l,:].conj()))**2 scalar_products.append(scalar_product) return scalar_products return ( error_QPM, generate_random_complex_gaussian_matrix, orthonormalize_vectors_svd, scalar_products_QPM, ) @app.cell def _(): import marimo as mo import numpy as np import matplotlib.pyplot as plt return mo, np, plt @app.cell def _( button, eps_slider, error_QPM, generate_random_complex_gaussian_matrix, max_iter_slider, n_slider, orthonormalize_vectors_svd, scalar_products_QPM, ): button u = generate_random_complex_gaussian_matrix(n_slider.value) error_tolerance = 10**(-eps_slider.value) max_iter = max_iter_slider.value iter = 0 error = error_QPM(u) errors = [error] # Initialize a list to store errors scalar_products = scalar_products_QPM(u) # Initialize the scalar product list while error > error_tolerance and iter < max_iter: # orthonormalize rows for i in range(n_slider.value): u[i, :, :] = orthonormalize_vectors_svd(u[i, :, :]) # orthonormalize columns for j in range(n_slider.value): u[:, j, :] = orthonormalize_vectors_svd(u[:, j, :]) error = error_QPM(u) errors.append(error) # Append the current error to the list if iter % 10 == 0: scalar_products = scalar_products_QPM(u) # Update scalar prodcuts iter += 1 return ( error, error_tolerance, errors, i, iter, j, max_iter, scalar_products, u, ) @app.cell def _(): return if __name__ == "__main__": app.run()