Skip to main content
added 601 characters in body
Source Link
Chua KS
  • 487
  • 3
  • 7

If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by

$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\}$ and $A$ is the adjacency matrix.

Since we can also write $\Phi_G=\det( \sum_{j=1}^n x_jI_j-A)$, where $I_j$ is the matrix which is

$1$ at the $(j,j)$ position and zero elsewhere which are positive semi definite and $A$ is symmetric, $P=\Phi_G$ is real stable.

It follows we must have $\Delta_{ij}(P)=P_iP_j-PP_{ij} \ge 0$ as real valued function.

How does one prove that in the case of a tree $T$, $\Delta_{ij}(\Phi_T)=(\Phi_{T-[v_i,v_j]})^2,$

where $T-[v_i,v_j]$ means the forests given by $T$ with all vertices (include end points) on the unique path from $v_i$ to $v_j$ deleted ?

In case $G$ is not a tree, how to prove $\Phi_G$ is still a perfect square ? How to read off the square root from the graph?

(Added) The fact that $\Delta_{ij}(P)$ is a perfect square holds more generally if we take $A$ to be any Hermitian matrix. In that case $\Phi_A$ is still real stable but $D_{ij}$ may be non real and the matrix identity implies $\Delta_{ij}(\Phi_A)=|D_{ij}|^2$ so that it is either a square or a sum of two squares of real polynomials. The interpretation of $D_{ij}$ as polynomial of deleted path in the case of tree is less obvious and actually holds in any graph for which there is a unique path from $v_i$ to $v_j$. How can one read off $D_{ij}$ from the graph when there is more than one path ?

If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by

$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\}$ and $A$ is the adjacency matrix.

Since we can also write $\Phi_G=\det( \sum_{j=1}^n x_jI_j-A)$, where $I_j$ is the matrix which is

$1$ at the $(j,j)$ position and zero elsewhere which are positive semi definite and $A$ is symmetric, $P=\Phi_G$ is real stable.

It follows we must have $\Delta_{ij}(P)=P_iP_j-PP_{ij} \ge 0$ as real valued function.

How does one prove that in the case of a tree $T$, $\Delta_{ij}(\Phi_T)=(\Phi_{T-[v_i,v_j]})^2,$

where $T-[v_i,v_j]$ means the forests given by $T$ with all vertices (include end points) on the unique path from $v_i$ to $v_j$ deleted ?

In case $G$ is not a tree, how to prove $\Phi_G$ is still a perfect square ? How to read off the square root from the graph?

If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by

$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\}$ and $A$ is the adjacency matrix.

Since we can also write $\Phi_G=\det( \sum_{j=1}^n x_jI_j-A)$, where $I_j$ is the matrix which is

$1$ at the $(j,j)$ position and zero elsewhere which are positive semi definite and $A$ is symmetric, $P=\Phi_G$ is real stable.

It follows we must have $\Delta_{ij}(P)=P_iP_j-PP_{ij} \ge 0$ as real valued function.

How does one prove that in the case of a tree $T$, $\Delta_{ij}(\Phi_T)=(\Phi_{T-[v_i,v_j]})^2,$

where $T-[v_i,v_j]$ means the forests given by $T$ with all vertices (include end points) on the unique path from $v_i$ to $v_j$ deleted ?

In case $G$ is not a tree, how to prove $\Phi_G$ is still a perfect square ? How to read off the square root from the graph?

(Added) The fact that $\Delta_{ij}(P)$ is a perfect square holds more generally if we take $A$ to be any Hermitian matrix. In that case $\Phi_A$ is still real stable but $D_{ij}$ may be non real and the matrix identity implies $\Delta_{ij}(\Phi_A)=|D_{ij}|^2$ so that it is either a square or a sum of two squares of real polynomials. The interpretation of $D_{ij}$ as polynomial of deleted path in the case of tree is less obvious and actually holds in any graph for which there is a unique path from $v_i$ to $v_j$. How can one read off $D_{ij}$ from the graph when there is more than one path ?

added 125 characters in body; edited tags; edited title
Source Link
Chua KS
  • 487
  • 3
  • 7

How to prove that for the real stable characteristic polynomial $P=\Phi_T$ of a tree $T$, $P_iP_j-PP_{ij}=(\Phi_{T-[v_i,v_j]})^2$?

If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by

$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\}$ and $A$ is the adjacency matrix.

Since we can also write $\Phi_G=\det( \sum_{j=1}^n x_jI_j-A)$, where $I_j$ is the matrix which is

$1$ at the $(j,j)$ position and zero elsewhere which are positive semi definite and $A$ is symmetric, $P=\Phi_G$ is real stable.

It follows we must have $\Delta_{ij}(P)=P_iP_j-PP_{ij} \ge 0$ as real valued function.

How does one prove that in the case of a tree $T$, $\Delta_{ij}(\Phi_T)=(\Phi_{T-[v_i,v_j]})^2,$

where $T-[v_i,v_j]$ means the forests given by $T$ with all vertices (include end points) on the unique path from $v_i$ to $v_j$ deleted ?

deletedIn case $G$ is not a tree, how to prove $\Phi_G$ is still a perfect square ? How to read off the square root from the graph?

How to prove that for the characteristic polynomial $P=\Phi_T$ of a tree $T$, $P_iP_j-PP_{ij}=(\Phi_{T-[v_i,v_j]})^2$?

If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by

$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\}$ and $A$ is the adjacency matrix.

Since we can also write $\Phi_G=\det( \sum_{j=1}^n x_jI_j-A)$, where $I_j$ is the matrix which is

$1$ at the $(j,j)$ position and zero elsewhere which are positive semi definite and $A$ is symmetric, $P=\Phi_G$ is real stable.

It follows we must have $\Delta_{ij}(P)=P_iP_j-PP_{ij} \ge 0$ as real valued function.

How does one prove that in the case of a tree $T$, $\Delta_{ij}(\Phi_T)=(\Phi_{T-[v_i,v_j]})^2,$

where $T-[v_i,v_j]$ means the forests given by $T$ with all vertices (include end points) on the unique path from $v_i$ to $v_j$

deleted ?

How to prove that for the real stable characteristic polynomial $P=\Phi_T$ of a tree $T$, $P_iP_j-PP_{ij}=(\Phi_{T-[v_i,v_j]})^2$?

If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by

$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\}$ and $A$ is the adjacency matrix.

Since we can also write $\Phi_G=\det( \sum_{j=1}^n x_jI_j-A)$, where $I_j$ is the matrix which is

$1$ at the $(j,j)$ position and zero elsewhere which are positive semi definite and $A$ is symmetric, $P=\Phi_G$ is real stable.

It follows we must have $\Delta_{ij}(P)=P_iP_j-PP_{ij} \ge 0$ as real valued function.

How does one prove that in the case of a tree $T$, $\Delta_{ij}(\Phi_T)=(\Phi_{T-[v_i,v_j]})^2,$

where $T-[v_i,v_j]$ means the forests given by $T$ with all vertices (include end points) on the unique path from $v_i$ to $v_j$ deleted ?

In case $G$ is not a tree, how to prove $\Phi_G$ is still a perfect square ? How to read off the square root from the graph?

Source Link
Chua KS
  • 487
  • 3
  • 7

How to prove that for the characteristic polynomial $P=\Phi_T$ of a tree $T$, $P_iP_j-PP_{ij}=(\Phi_{T-[v_i,v_j]})^2$?

If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by

$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\}$ and $A$ is the adjacency matrix.

Since we can also write $\Phi_G=\det( \sum_{j=1}^n x_jI_j-A)$, where $I_j$ is the matrix which is

$1$ at the $(j,j)$ position and zero elsewhere which are positive semi definite and $A$ is symmetric, $P=\Phi_G$ is real stable.

It follows we must have $\Delta_{ij}(P)=P_iP_j-PP_{ij} \ge 0$ as real valued function.

How does one prove that in the case of a tree $T$, $\Delta_{ij}(\Phi_T)=(\Phi_{T-[v_i,v_j]})^2,$

where $T-[v_i,v_j]$ means the forests given by $T$ with all vertices (include end points) on the unique path from $v_i$ to $v_j$

deleted ?