Given a $\pmb{A}\in\mathbb{R}^{n\times n},\ \pmb{A}^T=\pmb{A},\ \pmb{A}_{ii}=0$, is it possible, to generate via operations of linear algebra $\pmb{B}\in\mathbb{R}^{n\times n}:\ \pmb{B}_{ij}=\pmb{A}_{ij}+\pmb{\pi}_i+\pmb{\pi}_j,\ \pmb{B}_{ii}=0$, i.e. to formulate the adding of vertex potentials that are utilized in Held and Karp's calculation of high lower bounds on the length of the optimal solution of a symmetric traveling salesman problem?

It is fairly easy without the restriction of using operations from linear algebra and agreeing on column vectors:
$\pmb{\pi}\in\mathbb{R}^n,\ \pmb{e}\in\mathbb{R}^n,\pmb{e}_i=1\ \implies\ \pmb{B}=\pmb{A}+\pmb{\pi}\pmb{e}^T+\pmb{e}\pmb{\pi}^T-2 diag(\pmb{\pi})$, so the question boils down to as to whether it is possible to generate a diagonal matrix, whose diagonal elements resemble that of a given vector, from a vector with linear algebraic operations.

The existence of such an operation would be helpful in a proof of properties of vertex potentials that are calculated from the entries of $\pmb{A}$ or, put differently, whether it is possible to calculate a "ground state" of symmetric matrices by annihilating vertex potentials.

The following two images depict the effect of removing vertex potentials on the Minimum Spanning Tree of a planar pointset:

MST of 3000 points with euclidean distance as edgeweights

MST of 3000 points with euclidena distance and vertex potentials removed

The red dotted lines depict the convex hull of the 3000 points; removing the vertex weights incurs some kind of shape sensitivity to the MST and it is remarkable that it contains a very long path that almost resembles a hull of the pointset.


Let $\mathbf{d}$ be the diagonal matrix with $1,2,\ldots,n$ on the diagonal. Denote by $\pmb{\pi} \mapsto A\cdot \pmb{\pi}$ the application of a linear map $A\colon \mathbb{R}^{n\times n} \to \mathbb{R}^{n\times n}$ on the space of matrices. In particular, denote $[\mathbf{d},-]\cdot \pmb{\pi} = \mathbf{d}\pmb{\pi} - \pmb{\pi}\mathbf{d}$. Then $$ \operatorname{diag}(\pmb{\pi}) = \frac{\sin(2\pi[\mathbf{d},-])}{2\pi [\mathbf{d},-]} \cdot \pmb{\pi} , $$ which is easy to check by diagonalizing $[\mathbf{d},-]$ over the space of matrices.

I don't know if this is sufficiently within the realm of "matrix operations" for your purposes.

| cite | improve this answer | |

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.