Where did this useful matrix decomposition come from for Nodal Analysis?
I'm no mathematician but I feel strongly this is related to the singular value decomposition (SVD) or eigendecomposition.

I first came across SVD in the context of modelling MIMO communication systems, particularly those using spatial multiplexing. I'll try to detail this to explain why I think it relates to your problem which I am not able to answer directly.

Consider a time-invariant, noiseless MIMO channel. This can be represented as.

\$
\mathbf{y} = H(\omega)\mathbf{x}
\$

Where H is a matrix of transfer functions between the various parallel channels. Ideally, H would be diagonal and there would be no coupling between each channel. The presence of off-diagonal entries means that equalization will be required to prevent the channels interfering.

The SVD decomposes H into 

\$
H = U\Lambda V^*
\$

Where \$U\$ and \$V\$ can be thought of as rotations and \$\Lambda \$ is a diagonal matrix that simply scales each channel individually. \$U\$ and \$V\$ are both unitary matrices, so their inverses are their conjugate transposes. The columns of U and V also form orthonormal basis, so they can be thought of as the natural 'coordinate system' for solving the problem.

Intuitively, it takes the input channels, which are not orthogonal, and applies a transformation at the input and output that makes the behavior of the channel very simple, just attenuation (the matrix \$\Lambda \$). 

This has application to equalization, if we pre-multiply our input signals with \$V\$, pass it through the channel, and apply \$U^*\$ to the output. We get,

\$
\mathbf{y} = U^*U\Lambda V^*V\mathbf{x} \\
\mathbf{y} = \Lambda \mathbf{x}
\$

Which gives us completely orthogonal channels that do not interfere. This reminds me very much of your problem, the connection matrices being the natural orthogonal basis to use, and the conductances simply scaling these. 

The SVD also has some interesting applications in image processing

Edit: The decomposition in question is definitely an eigenvalue decomposition, of which the SVD can be thought of as a generalization.