1D interpolation: finding a polynomial satisfying $\forall_i\ p(x_i)=y_i$ can be written as a system of linear equations, having well known Vandermonde determinant: $\det=\prod_{i<j} (x_i-x_j)$. Hence, the interpolation problem is well defined as long as the system of equations is determined ($\det\neq 0$), that is equivalent with condition of having no two repeating $x$-s.

I need something analogous for quadratic form in $n$ dimensions: we would like to find symmetric matrix $A$ satisfying $\forall_k\ f(x^k)=y_k$, where $f(x)=x^T A x$, this time $x^k$ are vectors.

We get a system of linear equations: $$ \forall_k\ \sum_i A_{ii} (x^k_i)^2 + 2\sum_{i<j} A_{ij} x_i^k x_j^k =y_k$$ for $D=n(n+1)/2$ coefficients of symmetric $A$.

In analogy to interpolation problem, having values in $D$ points, we would like to find $A$. However, it requires that $\det\neq 0$ for the above set of linear equations.

Is there known a compact form for this determinant? (in analogy to Vandermonde)

If not, are there some known conditions ensuring it is nonzero - making fitting quadratic form well defined? These conditions need to contain e.g. that no two points are in one line $(x^k=a\cdot x^l)$. In what I need we can assume that all points lie on a sphere.

Specifically, my motivation is that looking at eigenspaces of adjacency matrix, we can convert the graph isomorphism problem into a question if two sets of points differ only by rotation (page 9-11 here. For strongly regular graphs these points are on a sphere and form a very regular polyhedron. Hence, I wanted to use an affine space of quadratic forms defining "wobbling" ellipsoids, such that they intersect only in our set - then we could use characteristic polynomial to test if they differ only by rotation. The crucial question is if e.g. $\{x: x^T A x=1 \textrm{ for all }A=A_0 + a\cdot A_1\}$ doesn't add too many extra points to the description. Geometrically: if "wobbling" ellipsoids with fixed some points, what extra fixed points would their intersection have?

Here is example of 2D situation: describing two points as intersection of ellipses/hyperbolas. Intersection only adds symmetric ($-x$) points, the question is when it is true, also in higher dimensions: enter image description here

  • I have browsed your paper about P=NP. Very interesting. About the fact that two set of points differ by a certain rotation, do you the Procustes algorithm (testing with matrix $UV^T$ coming from a certain SVD decomposition ? Besides, you work on spectral theory of graphs on adjacency matrices ; sometimes laplacians of graphs (diagonal matrix of degrees minus adjacency matrix) can bring more information : you can find many many things about this theory in the very rich book "An introduction to the theory of Graph Spectra" by Cvetkovic, Rowlinson and Simic, Cambridge Ed. 2010. – Jean Marie Dec 3 '17 at 8:30
  • Thanks, it is far from proving P=NP (yet?), only tries to gather approaches which are not likely to be found by people usually working on it. E.g. Grassmann variables known mostly by solid state physicists - P!=NP says their representation needs exponential cost. Graph isomorphism is simpler, I will have to look at Procrustes ... I had some experience with rotational invariants using spherical harmonics - see slide 5 here. Quadratics seem promising, but might add too many extra points? – Jarek Duda Dec 3 '17 at 10:00
  • ps. regarding using laplacian of graph instead, for regular there is no difference of eigenspaces, and I have to admit that my background is rather in MERW ( en.wikipedia.org/wiki/Maximal_entropy_random_walk ), which uses eigendecomposition of just adjacency matrix - it is more natural for me. Laplacian is close to heat kernel, which can be also done with MERW - nice paper: citeseerx.ist.psu.edu/viewdoc/… – Jarek Duda Dec 3 '17 at 23:15
  • 1
    Related: mathoverflow.net/questions/188746/… – Dap Dec 8 '17 at 14:22

I am not certain that I fully answer your question. Tell me if such is the case.

Let me introduce the following notation, different from yours : let us set

$$Y_{ij}:=X_i^TAX_j \in \mathbb{R}.$$

With this notation, do we agree that the system of constraints can be written :

$$\tag{1}X^TAX=Y$$

where $X=[X_1|X_2|\cdots|X_n]$ ? (the columns of $X$ are the $X_i$s).

But (1) can be written, using Kronecker (=tensor) product $\otimes$ and operator "vec" (which means a conversion of a $n \times n$ matrix into a $n^2 \times 1$ column vector). See for that "Matrix equations" in (https://en.wikipedia.org/wiki/Kronecker_product):

$$\tag{2}\underbrace{(X^T \otimes X^T)}_{\text{known}}\underbrace{vec(A)}_{\text{unknown}}=\underbrace{vec(Y)}_{\text{known}}$$

where "the compact expression" $X^T \otimes X^T$ is a $n^2 \times n^2$ matrix .

Thus we have transformed the issue into the resolution of a linear system.

As

$$\det(X^T \otimes X^T)= \det(X^T)^{2n}, $$ (Determinant of the Kronecker Product of Two Matrices)

the condition for this system to have a unique solution is still $\det(X^T) \ne 0 \iff \det(X) \ne 0$.

A remark: one can wonder if the constraint of symmetry is taken into account: this is the case because in (2), $vec(A)$ and $vec(Y)$ correspond to symmetrical unknowns (for $A$) and symmetrical data (for $Y$).

  • Any comment ?.. – Jean Marie Dec 3 '17 at 8:31
  • Thank you, I am just starting today - I have to look closer, but at the first look there is a dimensionality problem: the number of A coefficients and so points is D=n(n+1)/2, so your N matrix is n x D, should I understand it that any n x n minor has det != 0? – Jarek Duda Dec 3 '17 at 9:44
  • I understand your argument. I am going to take (maybe this evening) a simple example in order to see (first for me) how it works. – Jean Marie Dec 3 '17 at 9:49
  • And we don't know the entire Y, only its diagonal ... maybe seeing A in diagonal form could help: A = O^T D O ... – Jarek Duda Dec 3 '17 at 11:21
  • About procrustes analysis, I like this overview by Higham, a prominent numerical analyst (www.maths.manchester.ac.uk/~higham/talks/procrust94.ps.gz) – Jean Marie Dec 3 '17 at 11:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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