PROCRUSTES PROBLEM THE MYTH OF THESEUS
Orthogonal Procrustes problem and Graph Isomorphism problem.
In the Greek Mythology, Procrustes was a bandit who kept an inn in the path from Troezen to Athens. He was cruel and evil, and had a unique iron bed in his hostel. If a guest was too short for the bed, then he would stretch him or her to death until the size of the body was exactly the same of the bed. If the guest was too tall, the same goal would have to be attained, this time by choping the feet of the victim.
This terrible history gave name to a famous mathematical problem, which is usually written in terms of matrix transformations: given two matrices A and B, find the matrix C (among those in some predefined class) such that CA-B is the closest to zero. The problem is also stated with two allowed transformation matrices: find C and D such that ACD-B is the closest to zero.
The relation with the myth is quite direct: “A” is the guest, “B” is the bed and “C” (or “C,D”) is the treatment applied by Procrustes.
Different choices for the predefined class where the transformation matrices leave yield different concrete versions of the Procrustes problem, many of which correspond to well known and cellebrated applications of mathematics. For example, choosing C to be a permutation matrix one gets a problem of optimal scheduling for different tasks; choosing C and D to be permutation matrices yields the famous Graph Isomorphism Problem, and so on.
We tell you the Math and the Myth in this animated video.
FOR KIDS: Press the button below to download all the main characters and paint them as beautiful as you want!
