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


1 Answer 1


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
    Commented Jul 20, 2018 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
    Commented Jul 21, 2018 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
    Commented Jul 21, 2018 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
    Commented Jul 23, 2018 at 6:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .