The chapter discusses the concept of positive semidefinite rank (PSR) and its applications in distance geometry and convex set representation. Key points include: 1. **Euclidean Distance Matrices (EDMs)**: Schoenberg's theorem states that a matrix \( M \) is an EDM if and only if its diagonal entries are zero and the matrix formed by \( M_{1,i} + M_{1,j} - M_{i,j} \) for \( 2 \leq i, j \leq n \) is positive semidefinite. This allows certain distance geometry problems to be expressed as semidefinite programs (SDPs). 2. **Semidefinite Representation**: A convex set \( C \) can be represented using SDPs if it can be written as \( C = \pi(\mathbf{S}_+^d \cap L) \), where \( \mathbf{S}_+^d \) is the set of \( d \times d \) positive semidefinite matrices, \( L \) is an affine subspace, and \( \pi \) is a linear map. 3. **Examples of SDP Representations**: - \( EDM^{n+1} \) has an SDP representation of size \( n \). - A disk in \( \mathbb{R}^2 \) has an SDP representation of size 2. - A square \( [-1, 1]^2 \) has an SDP representation of size 3. 4. **Existential vs. Complexity Questions**: - **Existential Question**: Which convex sets admit an SDP representation? - **Complexity Question**: Given a convex set \( C \), what is the smallest SDP representation of \( C \)? 5. **Lifting and Polytopes**: - **Lifting**: The process of transforming a polytope \( P \) into a higher-dimensional polytope by adding constraints. - **Slack Matrix**: For a polytope \( P \) in \( \mathbb{R}^d \), the slack matrix \( M \) is a nonnegative matrix whose entries are the differences between the coordinates of facets and vertices of \( P \). 6. **Positive Semidefinite Rank (PSR)**: - **Definition**: The PSR of a matrix \( M \) is the size of the smallest PSD factorization \( M_{ij} = \text{Tr}(A_i B_j) \). - **Theorem (Gouveia, Parrilo, Thomas, 2011)**: The smallest SDP representation of a polytope \( P \) has size exactly \( \text{rank}_{\text{psd}}(M) \). 7. **LP vs. SDP Lifts**: - **LP Lifts**: A polytope \(The chapter discusses the concept of positive semidefinite rank (PSR) and its applications in distance geometry and convex set representation. Key points include: 1. **Euclidean Distance Matrices (EDMs)**: Schoenberg's theorem states that a matrix \( M \) is an EDM if and only if its diagonal entries are zero and the matrix formed by \( M_{1,i} + M_{1,j} - M_{i,j} \) for \( 2 \leq i, j \leq n \) is positive semidefinite. This allows certain distance geometry problems to be expressed as semidefinite programs (SDPs). 2. **Semidefinite Representation**: A convex set \( C \) can be represented using SDPs if it can be written as \( C = \pi(\mathbf{S}_+^d \cap L) \), where \( \mathbf{S}_+^d \) is the set of \( d \times d \) positive semidefinite matrices, \( L \) is an affine subspace, and \( \pi \) is a linear map. 3. **Examples of SDP Representations**: - \( EDM^{n+1} \) has an SDP representation of size \( n \). - A disk in \( \mathbb{R}^2 \) has an SDP representation of size 2. - A square \( [-1, 1]^2 \) has an SDP representation of size 3. 4. **Existential vs. Complexity Questions**: - **Existential Question**: Which convex sets admit an SDP representation? - **Complexity Question**: Given a convex set \( C \), what is the smallest SDP representation of \( C \)? 5. **Lifting and Polytopes**: - **Lifting**: The process of transforming a polytope \( P \) into a higher-dimensional polytope by adding constraints. - **Slack Matrix**: For a polytope \( P \) in \( \mathbb{R}^d \), the slack matrix \( M \) is a nonnegative matrix whose entries are the differences between the coordinates of facets and vertices of \( P \). 6. **Positive Semidefinite Rank (PSR)**: - **Definition**: The PSR of a matrix \( M \) is the size of the smallest PSD factorization \( M_{ij} = \text{Tr}(A_i B_j) \). - **Theorem (Gouveia, Parrilo, Thomas, 2011)**: The smallest SDP representation of a polytope \( P \) has size exactly \( \text{rank}_{\text{psd}}(M) \). 7. **LP vs. SDP Lifts**: - **LP Lifts**: A polytope \(