I am looking at these lecture notes: http://www.damtp.cam.ac.uk/user/hf323/M18-OPT/lecture16.pdf. In equation $(1)$, I am confused by the introduction of this notation: $$(p_S)_{ \substack{S\subseteq[n]\\|S|\leq 2k} }$$ and in equation $(3)$ by the notation: $$\big[y_{U\Delta V}\big]_{|U|,|V|\leq k} $$

Because the bracket notation is specified as positive semidefinite, I assume it denotes a matrix, although I'm not sure how exactly.

Analogously, I assume the parentheses notation denotes a vector, where each element is $p_S$ for some $S$ satisfying the conditions given in the subscript.

Could someone clarify this notation and specify exactly how it works?

  • $\begingroup$ I would assume that it's the same notation the author uses in lecture 15 $\endgroup$ – Saucy O'Path Dec 25 '18 at 23:53
  • $\begingroup$ @SaucyO'Path Where exactly are you looking? I don't see this in 15 $\endgroup$ – Dan Dec 26 '18 at 0:01
  • $\begingroup$ For instance, theorem 15.1 (in the second page) talks about a matrix $[Q_{U,V}]$ indexed over those pairs of subsets. It makes sense because you can choose any order on the sets (as long as it's the same for rows and columns) because conjugating by a permutation matrix does not change essentially a semidefinite matrix. $\endgroup$ – Saucy O'Path Dec 26 '18 at 0:04
  • $\begingroup$ I agree that he does have $Q_{U,V}$ as a matrix. But he doesn't use the bracket notation. It's also obvious (to me) that this is a matrix because it is indexed by $U$ and $V$ (ie two dimensions). In my question above, $[y_{U\Delta V}]$ just has the single index $U\Delta V$, which is a set: the symmetric difference of the sets $U$ and $V$. I'm not sure how lecture 15 answers this. $\endgroup$ – Dan Dec 26 '18 at 0:17
  • $\begingroup$ Ah, you are right, sorry. $\endgroup$ – Saucy O'Path Dec 26 '18 at 0:18

The notation $\big[y_{U\Delta V}\big]_{|U|,|V|\leq k}$ that was defined is also called $Y$ on the first line of page 2. After thinking about this a while, I can confirm this represents a matrix, where $Y_{U,V} = y_{U\Delta V} = y_S$, which we obtain from the corresponding element of the vector denoted by $(y_S)_{\substack{S\subseteq[n]\\|S|\leq 2k}}$.

In summary, we use elements from our vector $(y_S)$ to populate our matrix $[y_{U\Delta V}]$ such that the element in position $U,V$ of the matrix corresponds to the element in position $S=U\Delta V$ in the vector.

Yes, this does imply that the vector elements will be re-used many times in populating the matrix, as the symmetric difference ($\Delta$) of different $U,V$ values can result in the same $S$ value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.