Given a set of $\mathbb{R}^{m \times n}$ matrices, I would like to find the matrices forming the vertices of their convex hull.

Would this be the same problem as finding the convex hull of a set of vectors in $\mathbb{R}^{m + n}$? ie: Could I simply reshape the matrices into vectors and proceed with known algorithms to find the convex hull, and then convert back into $\mathbb{R}^{m \times n}$?

PS: Please be kind. I am a engineer with limited experience in this field. If you could point me to any references that could be helpful, I's appreciate it.



  1. My set of $\mathbb{R}^{m \times n}$ matrices is finite and each matrix is discrete.

  2. Some additional clarification: I am building this set up one matrix at a time. Each time I have a new matrix, I want to test if the new matrix is contained within the convex hull formed by the matrices already in the set. If it is, then I can ignore it. If it is not in the convex hull, then I add it to the set and extend the convex hull to include the new matrix.

  • $\begingroup$ Even in $\mathbb{R}^2$, the problem seems unclear. Circle is a convex shape. How do you define a vertex for a convex shape like circle? Also, on second paragraph of your question, you talk about finding the convex hull. Do you want to find the vertices given a set or find the convex hull given the vertices? $\endgroup$ – stressed out Feb 27 '19 at 0:38
  • $\begingroup$ This is a hard problem in general even with set of matrices with harmless looking properties. $\endgroup$ – chhro Feb 27 '19 at 0:39
  • $\begingroup$ stressed out, my set includes a finite number of matricies, so your example of a circle is not relevant to my problem, but is is a good example which illustrates why this a hard problem in general. Regarding the second paragraph, maybe a quick example will help explain. If I have a set of, say, 10 matrices, and 5 of these form the vertices of the convex hull which contains all 10, I want an algorithm that identifies these 5 vertex matrices. $\endgroup$ – drambugh Feb 27 '19 at 5:13

Since $\mathbb R^{m\times n}$ is isomorphic as a vector space to $\mathbb R^{mn}$ (note that that‘s not a plus) via the obvious map (taking all entries), you can indeed do the computation in $\mathbb R^{mn}$.


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.