# Inverse Eigenvalue problem for star graph

This is the problem:

Given $\lambda = [\lambda_1, \lambda_2, \cdots, \lambda_n]$ and $\mu = [\mu_1, \mu_2, \dots, \mu_{n-1}]$ build matrix $B$ such that its off-diagonal entries corresponds to a star graph (${v_iv_j \in E}$ if $B[i,j] \neq 0$) and eigenvalues of $B$ is $\lambda$ and eigenvalues of matrix $B_1$ which is matrix $B$ after removing the first row and column is $\mu$.

The Solution:

By interlacing theorem there must be:

$$\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \mu_2 \leq \cdots \leq \mu_{n-1}\leq \lambda_n$$

If we write $B$ as

$$B = \begin{bmatrix} a1&b^T\\b&M \end{bmatrix} =\begin{bmatrix} a1&b_1&b_2& \dots&b_{n-1}\\ b_1&\mu_1&0&\cdots&0\\ b_2&0&\mu_2&\cdots&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\\ b_{n-1}&0&0&\cdots&\mu_{n-1} \end{bmatrix}$$

where $M = diag(\mu_1, \cdots, \mu_{n-1})$ and $b = \{b_1, \cdots, b_{n-1}\}$

By tracing condition

$a_1 = \sum_{i=1}^{n}\lambda_i - \sum_{i=1}^{n-1}\mu_i$

Now by considering eigenvector equations for $B (B[v_1 \cdots v_n]^T = \lambda [v_1 \cdots v_n]^T)$:

$$b_iv_1 + (\mu_i - \lambda)v_{i+1} = 0$$

$$(a_1 - \lambda)v_1 + \sum_{i=1}^{n-1}b_iv_{i+1} = 0$$

as a result

$$\lambda - a_1 - \sum_{i=1}^{n-1}\dfrac{b_i^2}{\lambda-\mu_i} = 0$$

What I can't understand and I would be appreciated if you explain are following statements:

This is to have roots $\lambda_1, \cdots, \lambda_n$, so that

$$\lambda - a_1 - \sum_{i=1}^{n-1}\dfrac{b_i^2}{\lambda-\mu_i} = \dfrac{\prod_{i=1}^n (\lambda-\lambda_i)}{\prod_{i=1}^{n-1} (\lambda-\mu_i)}$$

and hence

$$b_i^2 = \dfrac{-\prod_{j=1}^n (\mu_i-\lambda_j)}{\prod_{j=1,i \neq j}^{n-1} (\mu_i-\mu_j)} \hspace{10px} i =1 , \cdots, n-1$$

I implemented this using matlab and it works but I have problem with its proofs

The expression on the left hand side of, $$\lambda - a_1 - \sum_{i=1}^{n-1} \frac{b_i^2}{\lambda - \mu_i} = 0$$ as a function of $\lambda$, is rational. If you multiply it by $\prod_{i=1}^{N-1} \lambda - \mu_i$ it becomes a polynomial, which we know has roots at the $\lambda_i$, since it was derived from the eigenvalue equations. We are also assuming that the multiplicity of each eigenvalue is $1$.
This leads to the factorisation, $$\left (\lambda - a_1 - \sum_{i=1}^{n-1} \frac{b_i^2}{\lambda - \mu_i} \right) \left(\prod_{i=1}^{n-1} \lambda - \mu_i \right) = \prod_{i=1}^{n} (\lambda - \lambda_i )\hspace{2cm} \tag{1}$$ Dividing through by $\prod_{i=1}^{n-1} \lambda - \mu_i$ gives, $$\lambda - a_1 - \sum_{i=1}^{n-1} \frac{b_i^2}{\lambda - \mu_i} = \frac{ \prod_{i=1}^{n} (\lambda - \lambda_i)}{\prod_{i=1}^{n-1} ( \lambda - \mu_i) } \tag{2}$$ as required.
For the next part, start from Equation (1). We will multiply out, and then set $\lambda = \mu_k$. Firstly, multiplying out yields, $$(\lambda - a_1) \left( \prod_{j=1}^{n-1} \lambda - \mu_j \right) - \sum_{i=1}^{n-1} \frac{b_i^2 \left(\prod_{j=1}^{n-1} \lambda - \mu_j \right) }{\lambda - \mu_i} = \prod_{i=1}^n( \lambda - \lambda_i) \tag{3}$$ Setting $\lambda = \mu_k$ makes the the far left hand term, on the left hand side, zero. After cancelling the denominators of the middle terms, we are left with, $$- b_k^2 \left(\prod_{i=1, i\neq k}(\mu_k - \mu_i) \right)= \prod_{i=1}^n (\mu_k - \lambda_i) \tag{4}$$ It then follows that, $$b_k^2 = - \frac{\prod_{i=1}^n (\mu_k - \lambda_i) }{\prod_{i=1, i\neq k}(\mu_k - \mu_i) } \tag{5}$$ as required.
• The left hand side of Equation 1 is a polynomial of degree $n$ in lambda, and so it has $n$ roots by the Fundamental Theorem of Algebra. – Damien Jul 21 '18 at 10:18
• For the second part, I can't understand why did you set the $\lambda = \mu_k$? Why didn't you set this to anything else? Also $\mu_k$ will be the zero of denominator and numerator of the middle term. Can we cancel the zeros from denominator and numerator? – M a m a D Jul 21 '18 at 17:13
• The $\lambda$ is a variable in the polynomial and so we can set it arbitrarily. The task was to find the values of $b_k$, and so we set $\lambda = \mu_k$ in Equation (3) because it simplifies to Equation (4). It is the simplest way to get to the $b_k$, you could instead choose $n$ different, distinct, values, and get a matrix equation for $b_k$. – Damien Jul 23 '18 at 6:44