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.

  • $\begingroup$ I have a question that I forgot to ask. How did you get the factorization of equation (1)? $\endgroup$ – M a m a D Jul 20 '18 at 7:39
  • $\begingroup$ 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. $\endgroup$ – Damien Jul 21 '18 at 10:18
  • $\begingroup$ 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? $\endgroup$ – M a m a D Jul 21 '18 at 17:13
  • 1
    $\begingroup$ 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$. $\endgroup$ – Damien Jul 23 '18 at 6:44

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.