# Indonesian Text-to-Image Synthesis with Sentence-BERT and FastGAN

Made Raharja Surya Mahadi1 and Nugraha Priya Utama1

(1School of Engineering and Informatics Institute Technology Bandung
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
)

###### Abstract

_Currently, text-to-image synthesis uses text encoder and image generator
architecture. Research on this topic is challenging. This is because of the
domain gap between natural language and vision. Nowadays, most research on
this topic only focuses on producing a photo-realistic image, but the other
domain, in this case, is the language, which is less concentrated. A lot of
the current research uses English as the input text. Besides, there are many
languages around the world. Bahasa Indonesia, as the official language of
Indonesia, is quite popular. This language has been taught in Philipines,
Australia, and Japan. Translating or recreating a new dataset into another
language with good quality will cost a lot. Research on this domain is
necessary because we need to examine how the image generator performs in other
languages besides generating photo-realistic images. To achieve this, we
translate the CUB dataset into Bahasa using google translate and manually by
humans. We use Sentence BERT as the text encoder and FastGAN as the image
generator. FastGAN uses lots of skip excitation modules and auto-encoder to
generate an image with resolution $512\times 512\times 3$, which is twice as
bigger as the current state-of-the-art model [Zhang2019]. We also get $4.76\pm
0.43$ and $46.401$ on Inception Score and Fréchet inception distance,
respectively, and comparable with the current English text-to-image generation
models. The mean opinion score also gives as $3.22$ out of 5, which means the
generated image is acceptable by humans._ Link to source code:
https://github.com/share424/Indonesian-Text-to-Image-synthesis-with-Sentence-
BERT-and-FastGAN

Keywords: Generative Adversarial Networks, Text-to-Image Synthesis, Bahasa
Indonesia

##  1 Introduction

Text-to-Image generation is challenging task because there is a domain gap
between natural language and vision. Nowadays, researchers use text encoder
and image generator architecture to produce photo-realistic images [Reed2016,
Zhang2019, Qiao2019, Tsue2020, Hu2021, Xu2018]. They use CNN-LSTM as the text
encoder and Generative Adversarial Networks proposed by goodfellow14 as the
image generator.

Lots of research in this area focus on how to generate a photo-realistic
image, but on the other hand, research on the language area is rarely done.
There is a thousand language across the world. One of the popular languages in
South-East Asia is Bahasa Indonesia. Bahasa Indonesia is the official language
of Indonesia and has been taught in the Philippines, Australia, and Japan.
This language is also used in other countries such as Canada, Vietnamese, and
Ukraine.

The main problem why research in this area is rarely done is because
translating or creating a new dataset with good quality for those languages
needs much cost. To examine how well text-to-image generation models perform
in other languages, we translate the dataset using Google Translate. To
increase the translation result, we also manually translate some of them.

To maintain the resolution of the generated image, we use FastGAN [Liuf2021]
as the image generator, which is can generate high-resolution image and
comparable with StyleGAN2 [Karras2020]. FastGAN proposed a skip excitation
module, which is a skip connection layer. This architecture can generate a
high-resolution image in just minimal iteration. The discriminator used auto-
encoder-like architecture to distinguish real and fake images. To get better
results, we also use Sentence-BERT [Reimers2020] as the text encoder.
Sentence-BERT can produce text embedding with lower cosine similarity on
similar semantic sentence and vice versa.

##  2 Related Works

Nowadays, text-to-image generation uses a text encoder and image generator
architecture. Mansimov2016 first proposed a method that uses deep learning,
where LSTM as the text encoder and DRAW as the image generator. This method
will generate an image by patches based on the attended features on the text.
Next, Reed2016 uses Generative Adversarial Networks [goodfellow14] as the
image generator, and CNN-LSTM as the text encoder. The text encoder generates
text embedding and concatenates it with random vector $Z\sim\mathcal{N}(0,1)$.
This latent vector is also used as input in the discriminator, making the
discriminator distinguish wrong images.

In order to generate high-resolution image, Zhang2019 uses a stack of GAN to
generate an image from low features to higher features. They proposed
Conditioning Augmentation networks to generate smooth latent vectors and small
random perturbations to increase the generated images variations. They also
proposed a JCU discriminator to perform the unconditional and conditional
tasks. The unconditional GAN discriminator can only distinguish between real
and fake images, and the conditional GAN discriminator can distinguish real,
fakes, and wrong images. They use three stacks of GAN: the first GAN generates
$64\times 64$ images, the second GAN generates $128\times 128$ images, and the
last GAN generates $256\times 256$. This method becomes the first and state-
of-the-art photo-realistic text to image generation.

Xu2018 proposed Attention GAN to improve the generated image using word-level
attention. They proposed a new Deep Attentional Multimodal Similarity Model
(DAMSM) to perform the attention. While Qiao2019 use different approaches by
improving the learning text-to-image generation idea using their proposed new
module, Semantic Text Module (STEM), Global-Local collaborative Attentive
Module in Cascaded Image Generators (GLAM), and Semantic Text Regeneration and
Alignment Module (STREAM). STEM perform text embedding using global sentence
features and word-level features. GLAM is a multi-stage Generator to generate
a realistic image. STREAM is an image captioning module that semantically
aligns with the given text descriptions.

In the same year, Qiao22019 also proposed a new method to perform text-to-
image generation, which is inspired by how humans draw a picture from a given
description. To mimic this process, they propose LeicaGAN, which consists of
three-phase, firstly is multiple priors learning via Textual-Visual Co-
Embedding (TVE), next is Imagination via Multiple Priors Aggregations (MPA),
and the last one is Creation via Cascaded Attentive Generator (CAG). TVE is a
module that generates text embedding with the same common semantic space as an
image. MPA is used to imagine what image will be generated. The text embedding
and text mask from the TVE module are used to convey visual information about
the semantics, textures, colors, shapes, and layouts. CAG module is the actual
generator module to produce the image.

To improve the attention results from Xu2018, Tsue2020 use BERT [Devlin2019]
as the text encoder and CycleGAN [Zhu2017] as the Generator. They proposed a
new cyclic design to learn and map the generated image back to text
descriptions. This method increases the inception score significantly.

Currently, to generate high-resolution images, researchers use a multi-stage
generator. This makes the model size is significantly huge. Liu2021 proposed
new lightweight GAN architecture that can be trained on a small amount of
image and minimum computing cost to generate a high-resolution image on
$1024\times 1024$. They use skip-layer channel-wise excitation module and an
auto-encoder-like discriminator to generate a high-resolution image that can
be compared to the state-of-the-art StyleGAN2 [Karras2020].

Many research focuses on generating high-resolution images and semantically
correct with the given text description. But research on the text encoder and
other languages is necessary. CNN-LSTM has become popular text embedding since
Reed2016 use that method. Then Xu2018 improve the text encoder with word-level
attention to improve the generated image details. And then Tsue2020 use BERT
as text encoder and word embedding. One of the BERT variants that is suitable
for sentence embedding is Sentence BERT [Reimers2020]. This variant uses a
siamese architecture network to produce text embedding that can then be
compared with cosine similarity to find sentence with similar meanings.

##  3 Dataset

In this research, we only use CUB dataset [WahCUB_200_2011] and translated
into Bahasa Indonesia using google translate and manually by humans. This
dataset contains 200 birds species and almost 12k images. Each image has $10$
captions in English. We split the dataset into $8.855$ as training data and
$2.933$ as validation data. This makes the total captions for training data is
$88.550$ and $29.330$ for the validation data. Because we use google translate
as the translation tool, we cannot expect the translation results grammarly
correct. So we were trying to fix this as much as possible manually.

##  4 Method

###  4.1 Text Encoder

To generate an image from a given text description, we need to extract the
feature from the given text and use that feature as input to the image
generator. The easiest way to achieve this is to use text embedding. Current
state-of-the-art language modeling is BERT [Devlin2019], and their variant for
generating text embedding is Sentence BERT [Reimers2020]. This architecture
uses a siamese network to perform the training process.

Figure 1: Our Generator Architecture. The blue box and arrow represent the
same up-sampling structure, the Yellow box represents the features map on the
spatial size, and the red box represents the skip-layer excitation module.

Usually, BERT produces a sequence of word features. The easiest way to
generate a single fixed-vector as the text embedding is to feed the output
into the pooling layer. As seen in the figure 1, the output from the BERT is
forwarded into the pooling layer to generate a fixed vector. We can feed the
feature into fully connected layers to generate different vector sizes.

To train this module, first, we need to pre-train the BERT. Currently, there
are state-of-the-art pre-trained BERT models in Bahasa Indonesia trained by
[cahya] using 522MB of Indonesian Wikipedia. This model is uncased and trained
under Masked Language Modeling (MLM) objective. The generated word features
vector shape is $786$. We increase the output size to $1024$ using a fully
connected layer.

Next, fine-tune the model using siamese network architecture. The loss
function plays an important role here because it can determine how well the
model performs on a specific task. We use cosine similarity loss with
$[0.8,1)$ on positive pair and $[0.4,0.6]$ on negative pair. Sentence with
same image class is positive pair and vice versa. Because every sentence on
the dataset talks about birds, we did not use the non-zero label on the
negative pair.

###  4.2 Image Generator

To perform image generation, we need a model that can generate images from
given features vector from the text encoder. To achieve this, we can use
Generative Adversarial Networks (GAN) [goodfellow14]. GAN can generate high-
resolution images from a single latent vector. To build GAN architecture, we
need a generator and discriminator. Generator and discriminator need input
from the text encoder to distinguish real, fake, and wrong images.

In order to generate high-resolution images, we use FastGAN [Liuf2021] as the
image generator. We can train this model with minimal effort to generate high-
resolution images. Data augmentation plays an important role in this
architecture.

####  4.2.1 Generator

Liuf2021 proposed a novel skip-layer excitation module with reformulate the
skip-connection idea from ResNet [He2016]. They use channel-wise
multiplication between the activations to reduce the computational cost. Since
the channel-wise multiplication does not require equal spatial dimension, we
can perform a skip-connection layer between longer range resolutions, making a
long shortcut to the gradient flow.

Skip excitation module can be defined as:

$y=F(x_{low},\\{W_{i}\\})\cdot x_{high}$ (1)

Where x is the input feature, and y is the output feature-maps, the function
$F$ performs the operation on the lower feature of $x$, and $W_{i}$ is the
weights to be learned.

Figure 1 illustrate our Generator architecture with the output image is
$512\times 512\times 3$. In order to generate diversity image from a single
text description, We use the conditioning variable $\hat{c}$ from CA-net
[Zhang2019] and concatenate it with the random vector
$z\thicksim\mathcal{N}(0,1)$. To obtain $\hat{c}$, we can use equation 2

$\hat{c}=\mu+\sigma\odot\omega$ (2)

Feed the text embedding $\varphi_{t}$ into a fully connected layer to obtain
$\mu$ and $\sigma$ (first-half element is $\mu$ and the rest is $\sigma$). The
$\odot$ symbol is element-wise multiplication. The output dimension of the
$\hat{c}$ is $128$, and the $z$ dimension is $100$, which makes our latent
vector dimension is $228$. We find that normal distribution performs better
than the uniform distribution for generating $z$ vector.

####  4.2.2 Discriminator

In order to perform strong regularization of the discriminator, we can treat
the discriminator as auto-encoder-like architecture. There are differences
with typical auto-encoder architecture, where the discriminator only decodes
the image for real images on small resolution. The discriminator also performs
a random crop with $\frac{1}{8}$ of its height and width on both input real
images and the generated image from the decoder. The decoder only consists of
$4\times$ nearest up-sampling layer, $3\times 3$ convolution layer, Batch
Normalization, and GLU activation function. This technique makes the
discriminator learn how to reproduce the input image.

Figure 2: Our Discriminator Architecture. Blue box and arrow represent the
same down-sampling structure, Yellow box represent the features map on the
spatial size, and red box represent the decoder module

In order to perform conditional GAN, we use the $\mu(\varphi_{t})$ from the
CA-net and concatenate it with the extracted feature from the discriminator,
where $\varphi_{t}$ is the text embedding. To calculate the total loss of this
architecture, we divide it into two conditions. The first is when the input is
the real images. We use perceptual loss [Zhang2018] to the auto-encoder-like
architecture and hinge adversarial loss [lim2017geometric] to the
discriminator output and sum the total. And the last one is when the input is
the fake or wrong image, we only use the hinge adversarial loss from the
generator output.

We can define the loss function for the generator and discriminator as:

$\begin{split}\mathcal{L}_{percept}&=\mathbb{E}_{f\thicksim
D_{encode}(x),x\thicksim I_{real}}[\|\mathcal{G}(f)-\mathcal{T}(x)\|]\\\
\mathcal{L}_{D}&=-\mathbb{E}_{x\thicksim I_{real}}[min(0,-1+D(x,\mu))]\\\
&\quad-\mathbb{E}_{x^{\prime}\thicksim
I_{wrong}}[min(0,-1-D(x^{\prime},\mu))]\\\ &\quad-\mathbb{E}_{\hat{x}\thicksim
G(z,\hat{c})}[min(0,-1-D(\hat{x},\mu))]\\\ &\quad+\mathcal{L}_{percept}\\\
\mathcal{L}_{G}&=-\mathbb{E}_{z\thicksim\mathcal{N}}[D(G(z,\hat{c}),\mu)]\end{split}$
(3)

where $\mathcal{L}_{percept}$ is the perceptual loss from [Zhang2018], $\mu$
is the variational text embedding from equation 2.

##  5 Experiment

###  5.1 Training Details

In this section will explain the training details for both text encoder and
image generator in this research.

####  5.1.1 Text Encoder

In order to train Sentence BERT, we need pre-trained BERT models. In this
research, we use [cahya] pre-trained BERT on Bahasa Indonesia language. We
need appropriate labels for both positive and negative pairs to get better
results. In the section 4.1, we explain that we use $[0.8,1)$ as the positive
pair label and $[0.4,0.6]$ as the negative pair labels. To train Sentence
BERT, we pass both sentences in the pair to the same networks, compare them
with cosine similarity, and perform mean-squared error to calculate the loss
value. We train our models for 10 epochs and save the best model only.

####  5.1.2 Image Generator

We perform both unconditional and conditional tasks to compare the results. We
train our models within $50.000$ iterations and batch size 10. First, we
encode all text descriptions into their embedding vector $\varphi_{t}$.

Unconditional. In this part, we only feed the generator with random vector
$z\thicksim\mathcal{N}(0,1)$ and conditioning text embedding $\hat{c}$.
Because every image has 10 captions, we select one randomly and feed it into
CA-net. The real and fake images are then augmented with random color
brightness, saturation, contrast, and translation. Next, we calculate the loss
value to update the discriminator. For the real images, we perform both
perceptual and hinge loss from equation 3 (without the wrong image part).

Conditional. We perform the same things with the generator on the
unconditional task for this task. We feed real, wrong, and fake images with
the conditioning augmentation vector $\mu$ from the CA-net in the
discriminator. We calculate the loss using the equation 3.

###  5.2 Evaluation

To evaluate generative models is quite challenging because calculating the
suitability of the resulting image with the given text is challenging to do.
So we perform both quantitative and qualitative evaluation metrics.

Inception Score. This method calculates the distribution of the generated
images. It makes us can calculate how the objectness of the generated image.
Inception score is often used as an evaluation metric on generative models.

Fréchet inception distance. On the other hand, Fréchet inception distance
[Heusel2017] has a better approach. This method calculates the distance
between training and fake images data distribution. However, this method still
cannot evaluate how appropriate the generated image is with the given text
description.

Mean Opinion Score. In order to perform qualitative evaluation, we evaluate
our models by conducting a survey. The respondent will be given 10 pair of
fake images and their text description. Every fake image consists of 4
generated images. They will select one of them and then do scoring between 0
and 5. While 0 means the generated image is not appropriate with the given
text description and the image is not clear, and 5 means the generated image
is appropriate with the given text description and the generated image is
clear.

##  6 Results

We train both text encoder and image generator separately and then combine
them on evaluation. To investigate our models, we also compare them with
current state-of-the-art text-to-image synthesis models to examine how the
text encoder performs in a different language, especially Bahasa Indonesia.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0.76$$0.77$$0.78$$0.79$$0.8$$0.81$$0.82$$0.83$$Epoch$$CosinePearson$
Figure 3: Text encoder training results

As shown in figure 3, our text encoder reaches the best score at epoch 3
within 0.82 on cosine pearson. This means our text encoder can produce text
embedding with higher cosine similarity on the similar sentence and vice
versa.

Table 1: Evaluation results both on Inception Score and Fréchet inception distance compared with other English text-to-image generation models on CUB datasets Method | Inception Score | FID
---|---|---
AttGAN [Xu2018] | $4.36\pm 0.03$ | 23.98
StackGAN [Zhang2019] | $4.04\pm 0.05$ | 15.30
MirrorGAN [Qiao2019] | $4.56\pm 0.05$ | -
CycleGAN+BERT [Tsue2020] | 5.92 | -
SSA-GAN [Hu2021] | $5.17\pm 0.08$ | 15.61
Our Unconditional | $4.75\pm 0.19$ | 99.12
Our Conditional | $4.76\pm 0.43$ | $46.401$

The fréchet inception distance and inception score of our model compared with
other English text-to-image synthesis are shown in Table 1. Our model easily
beats StackGAN, AttentionGAN, and MirrorGAN on the inception score, which
means our model can generate high-quality objects. However, our FID is higher
than other models, which means our models, compared to the training data, have
different data distribution and makes our generated images different from our
datasets.

The Inception Score for our unconditional GAN is slightly lower than our
conditional GAN but has a much higher FID. This means our unconditional and
conditional GAN has the same objectness but different image data distribution
against the datasets.

Table 2: Examples of images generated by our Unconditional and Conditional GAN. The input sentences in English is ”A red bird perched on a tree branch”, ”This bird has yellow wing and black beak”, ”A bird with blue wing and red tail”, ”A blackbird perched on a tree”, and ”A yellow bird on the water” Sentence | Unconditional | Conditional
---|---|---
seekor burung merah yang hinggap di cabang pohon |  |
burung ini memiliki sayap berwarna kuning dengan paruh berwara hitam |  |
seekor burung dengan sayap berwarna biru dan ekor berwarna merah |  |
seekor burung hitam sedang bertengger di atas pohon |  |
seekor burung kuning di atas air |  |

As shown in Table 2, we find out that our unconditional GAN is on collapse
modes. This is a common problem on generative adversarial networks because the
generator always tries to produce a similar image to fool the discriminator.
This can happen when the discriminator cannot distinguish between fake and
real images from different inputs. On the other hand, the conditional GAN can
fix this problem using the conditioning augmentation from CA-net as input for
the discriminator.

The conditional GAN also produces some novel images. The generator tries to
generate a red bird with blue wings on the third output, which does not exist
in the datasets. However, there is a red bird with black wings, so the
generator is trying to change the wing color to blue. That makes the wing dark
blue. Furthermore, there is no yellow bird on the water in the dataset, but
the generator is trying to output that in the last sentence. So the generator
is trying to change the existing yellow bird background with something like
water.

Table 3: The mean opinion score for both our unconditional and conditional GAN Method | Mean Opinion Score
---|---
Our Unconditional | 1.41
Our Conditional | 3.22

In order to perform a qualitative evaluation, we conduct a survey and average
the results. As shown in Table 3, our conditional GAN easily beats our
unconditional GAN. The mean opinion score of the conditional GAN is 3.22,
which means our models are still acceptable by humans.

##  7 Conclusion

This research investigates the text-to-image synthesis performance in
different languages, especially Bahasa Indonesia. To break through the gap
between natural language and vision, we use the current state-of-the-art
sentence embedding, Sentence BERT as the text encoder. In order to generate
photo-realistic images within minimal training effort, we use FastGAN as the
image generator. We implement the Conditioning Augmentation network to make
the generated images more diverse and use its output as input for generator
and discriminator. This makes our conditional GAN perform superior to
generating novel images. Our proposed architecture can generate high-
resolution images using Bahasa Indonesia as the input language.

For future works, we suggest properly translating the datasets to produce a
high-quality language model. We find out that text embeddings play an
essential role in generating the image details. Implementing weighted sum on
the discriminator loss also can produce high-quality images. AttentionGAN
[Xu2018] become another alternative to produce high-quality details. Using
another challenging dataset such as COCO datasets [lin2014microsoft] or even
ImageNet datasets can evaluate the model performance on different image
distributions. It would be helpful to train the model longer to increase the
inception score and FID. Trying other GAN variants also can produce different
image resolutions, such as StyleGAN2 [Karras2020].

## References

  * [1] [Devlin et al.]Devlin, Chang, Lee Toutanova2019Devlin2019 Devlin, J., Chang, M. W., Lee, K. Toutanova, K. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding, NAACL HLT 2019 - 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies - Proceedings of the Conference 1(Mlm): 4171–4186.
  * [2] [Goodfellow et al.]Goodfellow, Pouget-Abadie, Mirza, Xu, Warde-Farley, Ozair, Courville Bengio2014goodfellow14 Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A. Bengio, Y. 2014.  Generative adversarial nets, in Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence K. Q. Weinberger (eds), Advances in Neural Information Processing Systems 27, Curran Associates, Inc., pp. 2672–2680.
http://papers.nips.cc/paper/5423-generative-adversarial-nets.pdf

  * [3] [He et al.]He, Zhang, Ren Sun2016He2016 He, K., Zhang, X., Ren, S. Sun, J. 2016.  Deep residual learning for image recognition, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2016-Decem: 770–778.
  * [4] [Heusel et al.]Heusel, Ramsauer, Unterthiner, Nessler Hochreiter2017Heusel2017 Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B. Hochreiter, S. 2017.  GANs trained by a two time-scale update rule converge to a local Nash equilibrium, Advances in Neural Information Processing Systems 2017-December(Nips): 6627–6638.
  * [5] [Hu et al.]Hu, Liao, Yang Rosenhahn2021Hu2021 Hu, K., Liao, W., Yang, M. Y. Rosenhahn, B. 2021.  Text to Image Generation with Semantic-Spatial Aware GAN, (1).
http://arxiv.org/abs/2104.00567

  * [6] [Karras et al.]Karras, Laine, Aittala, Hellsten, Lehtinen Aila2020Karras2020 Karras, T., Laine, S., Aittala, M., Hellsten, J., Lehtinen, J. Aila, T. 2020.  Analyzing and improving the image quality of stylegan, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition pp. 8107–8116.
  * [7] Lim Ye2017lim2017geometric Lim, J. H. Ye, J. C. 2017.  Geometric gan.
  * [8] [Lin et al.]Lin, Maire, Belongie, Bourdev, Girshick, Hays, Perona, Ramanan, Zitnick Dollár2014lin2014microsoft Lin, T.-Y., Maire, M., Belongie, S., Bourdev, L., Girshick, R., Hays, J., Perona, P., Ramanan, D., Zitnick, C. L. Dollár, P. 2014\.  Microsoft coco: Common objects in context.  cite arxiv:1405.0312Comment: 1) updated annotation pipeline description and figures; 2) added new section describing datasets splits; 3) updated author list.
http://arxiv.org/abs/1405.0312

  * [9] Liu, Zhu, Song Elgammal2021Liuf2021 Liu, B., Zhu, Y., Song, K. Elgammal, A. 2021.  Towards Faster and Stabilized GAN Training for High-fidelity Few-shot Image Synthesis, pp. 1–22.
http://arxiv.org/abs/2101.04775

  * [10] Liu, Lin, Cao, Hu, Wei, Zhang, Lin Guo2021Liu2021 Liu, Z., Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang, Z., Lin, S. Guo, B. 2021.  Swin Transformer: Hierarchical Vision Transformer using Shifted Windows.
http://arxiv.org/abs/2103.14030

  * [11] [Mansimov et al.]Mansimov, Parisotto, Ba Salakhutdinov2016Mansimov2016 Mansimov, E., Parisotto, E., Ba, J. L. Salakhutdinov, R. 2016\.  Generating images from captions with attention, 4th International Conference on Learning Representations, ICLR 2016 - Conference Track Proceedings pp. 1–12.
  * [12] [Qiao et al.]Qiao, Zhang, Xu Tao2019aQiao22019 Qiao, T., Zhang, J., Xu, D. Tao, D. 2019a.  Learn, imagine and create: Text-to-image generation from prior knowledge, Advances in Neural Information Processing Systems 32(NeurIPS): 1–11.
  * [13] [Qiao et al.]Qiao, Zhang, Xu Tao2019bQiao2019 Qiao, T., Zhang, J., Xu, D. Tao, D. 2019b.  Mirrorgan: Learning text-to-image generation by redescription, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2019-June: 1505–1514.
  * [14] [Reed et al.]Reed, Akata, Yan, Logeswaran, Schiele Lee2016Reed2016 Reed, S., Akata, Z., Yan, X., Logeswaran, L., Schiele, B. Lee, H. 2016\.  Generative adversarial text to image synthesis, 33rd International Conference on Machine Learning, ICML 2016 3: 1681–1690.
  * [15] Reimers Gurevych2020Reimers2020 Reimers, N. Gurevych, I. 2020.  Sentence-BERT: Sentence embeddings using siamese BERT-networks, EMNLP-IJCNLP 2019 - 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing, Proceedings of the Conference pp. 3982–3992.
  * [16] [Tsue et al.]Tsue, Li Sen2020Tsue2020 Tsue, T., Li, J. Sen, S. 2020.  Cycle Text-to-Image GAN with BERT, arXiv .
  * [17] [Wah et al.]Wah, Branson, Welinder, Perona Belongie2011WahCUB_200_2011 Wah, C., Branson, S., Welinder, P., Perona, P. Belongie, S. 2011\.  The Caltech-UCSD Birds-200-2011 Dataset, Technical Report CNS-TR-2011-001, California Institute of Technology.
  * [18] Wirawan2020cahya Wirawan, C. 2020.  Indonesian BERT base model (uncased), https://huggingface.co/cahya/bert-base-indonesian-522M.  [Online; accessed 30-August-2021].
  * [19] [Xu et al.]Xu, Zhang, Huang, Zhang, Gan, Huang He2018Xu2018 Xu, T., Zhang, P., Huang, Q., Zhang, H., Gan, Z., Huang, X. He, X. 2018\.  AttnGAN: Fine-Grained Text to Image Generation with Attentional Generative Adversarial Networks, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition pp. 1316–1324.
  * [20] [Zhang et al.]Zhang, Xu, Li, Zhang, Wang, Huang Metaxas2019Zhang2019 Zhang, H., Xu, T., Li, H., Zhang, S., Wang, X., Huang, X. Metaxas, D. N. 2019.  StackGAN++: Realistic Image Synthesis with Stacked Generative Adversarial Networks, IEEE Transactions on Pattern Analysis and Machine Intelligence 41(8): 1947–1962.
  * [21] [Zhang et al.]Zhang, Isola, Efros, Shechtman Wang2018Zhang2018 Zhang, R., Isola, P., Efros, A. A., Shechtman, E. Wang, O. 2018\.  The Unreasonable Effectiveness of Deep Features as a Perceptual Metric, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (1): 586–595.
  * [22] [Zhu et al.]Zhu, Park, Isola Efros2017Zhu2017 Zhu, J. Y., Park, T., Isola, P. Efros, A. A. 2017.  Unpaired Image-to-Image Translation Using Cycle-Consistent Adversarial Networks, Proceedings of the IEEE International Conference on Computer Vision 2017-Octob: 2242–2251.
  * [23]


# A complete characterization of spectra of the Randić matrix of level-wise
regular trees

Punit Vadher
Gujarat Technogical University, Ahmedabad - 382 424, Gujarat (INDIA)
E-mail<EMAIL_ADDRESS>

Devsi Bantva111Corresponding author.
Lukhdhirji Engineering College, Morvi - 363 642, Gujarat (INDIA)
E-mail<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a simple finite connected graph with vertex set
$V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Denote the degree of vertex $v_{i}$ by
$d_{i}$ for all $1\leq i\leq n$. The Randić matrix of $G$, denoted by
$\mbox{{R}}(G)=[r_{i,j}]$, is the $n\times n$ matrix whose $(i,j)$-entry
$r_{i,j}$ is $r_{i,j}=1/\sqrt{d_{i}d_{j}}$ if $v_{i}$ and $v_{j}$ are adjacent
in $G$ and 0 otherwise. A tree is a connected acyclic graph. A level-wise
regular tree is a tree rooted at one vertex $r$ or two (adjacent) vertices $r$
and $r^{\prime}$ in which all vertices with the minimum distance $i$ from $r$
or $r^{\prime}$ have the same degree $m_{i}$ for $0\leq i\leq h$, where $h$ is
the height of $T$. In this paper, we give a complete characterization of the
eigenvalues with their multiplicity of the Randić matrix of level-wise regular
trees. We prove that the eigenvalues of the Randić matrix of a level-wise
regular tree are the eigenvalues of the particular tridiagonal matrices, which
are formed using the degree sequence $(m_{0},m_{1},\ldots,m_{h-1})$ of level-
wise regular trees.

_Keywords:_ Graph spectrum, Randić matrix, Level-wise regular tree.

_AMS Subject Classification (2020): 15A18, 05C50, 05C05._

##  1 Introduction

The graphs considered in this paper are finite connected graphs without loops
or multiple edges. Denote $V(G)=\\{v_{1},v_{2},\dots,v_{n}\\}$ the vertex set
of graph $G$ and $d_{i}$ the degree of vertex $v_{i}$ for $i=1,2,\ldots,n$
(the degree of a vertex $v\in V(G)$ is the number of adjacent vertices to
$v$). In 1975, Randić [14] invented a molecular structure descriptor defined
as

$\mbox{{R}}\mbox{\rm{I}}(G)=\sum_{v_{i}\sim
v_{j}}\frac{1}{\sqrt{d_{i}d_{j}}},$

where the summation runs over all pairs of adjacent vertices of the underlying
(molecular) graph. This graph invariant is nowadays known as Randić index
named after Randić; for details refer [9, 11, 15, 17, 18]. The readers are
advised to refer [12] for a detail survey on the Randić index. Inspired by the
Randić index, a symmetric square matrix $\mbox{{R}}=\mbox{{R}}(G)$ of order
$n$ is associated to the graph $G$ known as Randić matrix of $G$, whose
$(i,j)$-entry $r_{i,j}$ is defined as

$r_{i,j}=\left\\{\begin{array}[]{ll}\frac{1}{\sqrt{d_{i}d_{j}}},&\mbox{ if
$v_{i}$ and $v_{j}$ are adjacent vertices in $G$},\\\\[5.69046pt] 0,&\mbox{
otherwise}.\end{array}\right.$

The Randić matrix $\mbox{{R}}(G)$ without this name was first studied in the
book [4] by Cvetković, Doob and Sachs (refer [10]). The matrix $\mbox{{R}}(G)$
was also used to study Randić index in 2005 by Rodríguez who called it the
weighted adjacency matrix in [17] and the degree adjacency matrix in [18]. The
R-characteristic polynomial of graph $G$ is the R-characteristic polynomial of
the Randić matrix R of graph $G$ which is
$\mbox{{R}}(\lambda)=\det(\lambda\mbox{\rm{I}}_{n}-\mbox{{R}})$, where
$\mbox{\rm{I}}_{n}$ is the identity matrix of size $n$. The Randić matrix is a
real symmetric matrix and hence the eigenvalues of R are real numbers. Denote
the eigenvalues of Randić matrix R by
$\rho_{1}\geq\rho_{2}\geq\ldots\geq\rho_{n}$ with multiplicity
$m_{1}(\rho_{1}),m_{2}(\rho_{2}),\ldots,m_{n}(\rho_{n})$. The R-spectrum of
graph $G$, denoted by $S_{R}(G)$, is

$S_{R}(G)=\bigg{(}\begin{matrix}\rho_{1}&\rho_{2}&\rho_{3}&...&\rho_{n}\\\
m_{1}(\rho_{1})&m_{2}(\rho_{2})&m_{3}(\rho_{3})&...&m_{n}(\rho_{n})\end{matrix}\bigg{)}.$

The relation between the eigenvalues of Randić matrix of graph $G$ and Randić
index of graph $G$ is as follows (see [3]):

$\sum_{i=1}^{n}\rho_{i}^{2}=2\cdot\mbox{{R}}\mbox{\rm{I}}(G).$

In [10], Gutman et al. gave the following important observations about
$\mbox{{R}}(G)$ (and it is worth to recall here in connection with our
results) while studying the Randić energy of graph $G$:

  * •

If $G$ has $k$ components, namely $G_{1},G_{2},\ldots,G_{k}$ then
$S_{R}(G)=S_{R}(G_{1})\cup S_{R}(G_{2})\cup\ldots\cup S_{R}(G_{k})$.

  * •

Let $\overline{K}_{n}$ be the complement of complete graph $K_{n}$ then
$S_{R}(\overline{K}_{n})=\bigg{(}\begin{matrix}0\\\ n\end{matrix}\bigg{)}.$

  * •

Let $G$ be a graph on $n\geq 1$ vertices and let $\rho_{1}$ be the greatest
eigenvalue of its Randić matrix. Then $\rho_{1}=0$ holds if and only if
$G\cong\overline{K}_{n}$. If $G$ has at least one edge, then $\rho_{1}=1$ (the
last statement is also proved in [13, Theorem 2.1]).

Moreover, Furtula and Gutman noted in [7] that the sum of eigenvalues of
Randić matrix of graph $G$ is equal to zero and the relations

$\rho_{i}=\rho_{n-i+1},\;\;i=1,2,\ldots,n$

holds if and only if the graph $G$ is bipartite.

The spectra of the Randić matrix is studied by many authors for different
purposes, like Randić index, Randić energy, structural information of graph
etc. (see [1, 5, 8]). In [1], Alikhani and Ghanbari gave the R-characteristic
polynomial (using it one can easily find R-spectrum) for path $P_{n}$, star
$K_{1,n-1}$, cycle $C_{n}$, complete graph $K_{n}$, complete bipartite graph
$K_{m,n}$ and friendship graphs $F_{n}$ and $D_{4}^{n}$ (refer [1] for
definitions of friendship graphs $F_{n}$ and $D_{4}^{n}$). In [22], Yin
studied the multiple Randić eigenvalues of trees. Andrade et al. studied the
Randić spectra of caterpillar graphs (a tree is called a caterpillar if the
removal of all its degree-one vertices results in a path) in [2]. Rather et
al. studied the Randić spectrum of zero divisor graphs of commutative ring
$\mathbb{Z}_{n}$ in [16]. The adjacency spectra and Laplacian spectra of
level-wise regular trees are studied in [19] and [20], respectively. Fernandes
et al. discussed the spectra of some graphs like weighted trees in [6].

In this paper, we completely characterize all the eigenvalues (with their
multiplicity) of the Randić matrix of the level-wise regular trees, a large
class of trees. In fact, we prove that the eigenvalues of the Randić matrix of
level-wise regular trees are the eigenvalues of the leading principal
submatrices of three symmetric tridiagonal matrices of order equal to the
height of level-wise regular trees plus one. This paper is organised as
follows: We define the necessary terms, notations and also recall some well-
known results of spectral theory in section 2. We represent the Randić matrix
of level-wise regular trees as a tridiagonal matrix of blocks, which we used
to prove our main result. The section 3 consists of three Lemmas (which are
useful to prove our main results) and two main Theorems. We illustrated the
whole procedure of main results with the help of two examples.

##  2 Preliminaries

In this section, we define necessary terms and notations to prove our main
results. We also recall some standard results that are necessary for the
present work.

A tree is a connected acyclic graph. A star on $n$ vertices, denoted by
$K_{1,n-1}$, is a tree consisting of $n-1$ leaves and another vertex joined to
all leaves by edges. A level-wise regular tree is a tree rooted at one vertex
$r$ or two (adjacent) vertices $r$ and $r^{\prime}$ in which all vertices with
the minimum distance, $i$ from $r$ or $r^{\prime}$ have the same degree
$m_{i}$ for $0\leq i\leq h$, where $h$ is the height of $T$. Denote the level-
wise regular tree by $T^{1}=T^{1}_{m_{0},m_{1},\ldots,m_{h-1}}$ (with one
root) and $T^{2}=T^{2}_{m_{0},m_{1},\ldots,m_{h-1}}$ (with two root). Observe
that the diameter of $T^{1}_{m_{0},m_{1},\ldots,m_{h-1}}$ is $2h$ and
$T^{2}_{m_{0},m_{1},\ldots,m_{h-1}}=2h+1$. The order of level-wise regular
tree $T^{z}=T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ is

$|V(T^{z})|=\left\\{\begin{array}[]{ll}1+m_{0}+m_{0}\sum_{t=1}^{h-1}\left(\prod_{k=1}^{t}(m_{k}-1)\right),&\mbox{if
$z=1$},\\\\[5.69046pt]
2+2\sum_{t=0}^{h-1}\left(\prod_{k=0}^{t}(m_{k}-1)\right),&\mbox{if
$z=2$}.\end{array}\right.$ (1)

In this work by a tree $T$ we mean a level-wise regular tree
$T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}$, where $z=1,2$. Moreover, we assume
$m_{0}\geq 2$ for $T^{1}=T^{1}_{m_{0},m_{1},\ldots,m_{h-1}}$ and $m_{0}\geq 3$
for $T^{2}=T^{2}_{m_{0},m_{1},\ldots,m_{h-1}}$. Denote $C(T^{1})=\\{r\\}$ and
$C(T^{2})=\\{r,r^{\prime}\\}$. In both cases, we put the $C(T^{z})$, where
$z=1,2$ at level $0$ then $T^{z}$ has $h$ levels. Thus the vertices in the
level $h$ have degree $m_{h}=1$. Define $h+1$ layers $L_{i},0\leq i\leq h$ of
level-wise regular tree $T^{z}=T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}(z=1,2)$ as

$L_{i}=\\{v\in V(T):\min\\{d(v,u):u\in C(T^{z})\\}=i\\}.$

Observe that $|L_{0}|=1,|L_{1}|=m_{0}$ for $T^{1}$ and
$|L_{0}|=2,|L_{1}|=2(m_{0}-1)$ for $T^{2}$ and for $2\leq i\leq h$,

$|L_{i}|=\left\\{\begin{array}[]{ll}m_{0}\prod_{k=1}^{i-1}(m_{k}-1),&\mbox{if
$|L_{0}|=1$},\\\\[5.69046pt] 2\prod_{k=0}^{i-1}(m_{k}-1),&\mbox{if
$|L_{0}|=2$}.\end{array}\right.$

Moreover, in a level-wise regular tree
$T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$, it is clear that for any $1\leq
i\leq h-1$, $|L_{i+1}|=(m_{i}-1)|L_{i}|$ and, $|L_{i}|=|L_{i+1}|$ if and only
if $m_{i}=2$. Observe that for all $j=0,1,\ldots,h-1$, $L_{j}$ divides
$L_{j+1}$.

We apply Algorithm 1 on vertices of
$T^{z}=T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ of order $n$ to give an
ordering $v_{1},v_{2},\ldots,v_{n}$ of $V(T^{z})$ to write Randić matrix of
$T^{z}$.

Algorithm 1 A vertex ordering $v_{1},v_{2},\ldots,v_{n}$ of
$V(T^{z}),\;z=1,2$.

Input: A vertex set $V(T^{z})$ of a tree $T^{z}$, where $z=1,2$.

1:$v_{1}\leftarrow u$ for any $u\in L_{h}$.

2:Set $k_{0}=0$ and $k_{i}=\sum_{t=1}^{i}|L_{h-i+1}|$ for $1\leq i\leq h-1$.

3:for $1\leq i\leq h-1$ do

4: for $1+k_{i-1}\leq j\leq k_{i}-1$ do

5: $v_{j+1}\leftarrow u$ for a $u\in L_{h-i+1}$ such that
$d(v_{j},v_{j+1})\leq d(v_{j},w)$ for any $w\in
L_{h-i+1}\setminus\\{v_{1},v_{2},\ldots,v_{j},u\\}$ and $v_{k_{i}+1}$ is a
parent of $v_{k_{i-1}+1}$.

6: end for

7:end for

8:$v_{n}\leftarrow r$ if $L_{0}=\\{r\\}$ and $v_{n-1}\leftarrow
r,v_{n}\leftarrow r^{\prime}$ such that $d(v_{1},v_{n-1})=h$ and
$d(v_{1},v_{n})=h+1$ if $L_{0}=\\{r,r^{\prime}\\}$.

9:return $\vec{V}:=\\{v_{1},v_{2},\ldots,v_{n}\\}$.

Output: A linear order $v_{1},v_{2},\ldots,v_{n}$ of $V(T^{z}),\;z=1,2$.

The readers can view the vertex ordering of tree
$T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ describe in Algorithm 1 in
Examples 2.2 and 2.3, respectively. We fix the ordering
$\\{v_{1},v_{2},\ldots,v_{n}\\}$ of vertices of level-wise regular tree
$T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ obtained by applying Algorithm 1
for all our subsequent discussion.

For $j=1,2,\ldots,h$, define $C_{j}$ is the column matrix of order
$\frac{|L_{h-j+1}|}{|L_{h-j}|}\times 1$ with each entry is equal to
$\frac{1}{\sqrt{m_{h-j+1}m_{h-j}}}$. That is,

$C_{j}=\begin{bmatrix}\frac{1}{\sqrt{m_{h-j}m_{h-j+1}}}&\\\
\frac{1}{\sqrt{m_{h-j}m_{h-j+1}}}&\\\ \vdots&\\\
\frac{1}{\sqrt{m_{h-j}m_{h-j+1}}}&\end{bmatrix}_{\frac{|L_{h-j+1}|}{|L_{h-j}|}\times
1}.$

For $j=1,2,\ldots,h$, let $B_{j}$ is the block diagonal matrix of order
$|L_{h-j+1}|\times|L_{h-j}|$ defined by

$B_{j}=\begin{bmatrix}C_{j}&0&\cdots&0\\\ 0&C_{j}&&\vdots\\\
\vdots&&\ddots&0\\\
0&\cdots&0&C_{j}\end{bmatrix}_{|L_{h-j+1}|\times|L_{h-j}|}$

######  Observation 2.1.

Let $T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}(z=1,2)$ be the level-wise regular
tree. Then the following hold for all $1\leq j\leq h$.

  1. (a)

$|L_{0}|\leq|L_{1}|\leq\ldots\leq|L_{h}|$ and for $1\leq j\leq h$,
$\frac{|L_{h-j+1}|}{|L_{h-j}|}$ is a positive integer,

  2. (b)

$C_{j}^{T}C_{j}=\frac{|L_{h-j+1}|}{|L_{h-j}|}\frac{1}{m_{h-j}m_{h-j+1}}$,

  3. (c)

$B_{j}^{T}B_{j}=\begin{bmatrix}C_{j}^{T}C_{j}&0&\cdots&0\\\
0&C_{j}^{T}C_{j}&&\vdots\\\ \vdots&&\ddots&0\\\
0&\cdots&0&C_{j}^{T}C_{j}\end{bmatrix}=\frac{|L_{h-j+1}|}{|L_{h-j}|}\frac{1}{m_{h-j}m_{h-j+1}}\mbox{\rm{I}}_{|L_{h-j}|}$,

  4. (d)

$\det(B_{j}^{T}B_{j})=\left(\frac{|L_{h-j+1}|}{|L_{h-j}|}\frac{1}{m_{h-j}m_{h-j+1}}\right)^{|L_{h-j}|}.$

We illustrate the above defined terms and notations with the help of the
following example of $T^{1}_{4,4,3}$ and $T^{2}_{4,3,4}$ for more clarity to
readers.

######  Example 2.2.

Let $T^{1}=T^{1}_{4,4,3}$ be the level-wise regular tree of height $3$ as
shown in the following Figure 1.

Figure 1: Tree $T^{1}_{4,4,3}$ and its vertex ordering.

Note that a tree $T^{1}_{4,4,3}$ has $4$ levels,
$|L_{0}|=1,|L_{1}|=4,|L_{2}|=12,|L_{3}|=24$ and the vertex degrees are
$m_{0}=4,m_{1}=4,m_{2}=3,m_{3}=1$. Then we have
$\frac{|L_{3}|}{|L_{2}|}=2,\frac{|L_{2}|}{|L_{1}|}=3$ and
$\frac{|L_{1}|}{|L_{0}|}=4$. Moreover, for $j=1,2,3$, the matrices $C_{j}$ are

$C_{1}=\begin{bmatrix}\frac{1}{\sqrt{3}}\\\\[5.69046pt]
\frac{1}{\sqrt{3}}\end{bmatrix}_{2\times
1},C_{2}=\begin{bmatrix}\frac{1}{2\sqrt{3}}\\\\[5.69046pt]
\frac{1}{2\sqrt{3}}\\\\[5.69046pt] \frac{1}{2\sqrt{3}}\end{bmatrix}_{3\times
1}\mbox{ and }C_{3}=\begin{bmatrix}\frac{1}{4}\\\\[2.84544pt]
\frac{1}{4}\\\\[2.84544pt] \frac{1}{4}\\\\[2.84544pt]
\frac{1}{4}\end{bmatrix}_{4\times 1}.$

Hence,

$B_{1}={\rm
diag}[C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1}]$
$B_{2}={\rm diag}[C_{2},C_{2},C_{2},C_{2}]$

and

$B_{3}={\rm diag}[C_{3}].$

The Randić matrix of the tree $T^{1}_{4,4,3}$ is

$\mbox{{R}}(T^{1})=\begin{bmatrix}0&B_{1}&0&0\\\ B_{1}^{T}&0&B_{2}&0\\\
0&B_{2}^{T}&0&B_{3}\\\ 0&0&B_{3}^{T}&0\end{bmatrix}.$

######  Example 2.3.

Let $T^{2}=T^{2}_{4,3,4}$ be the level wise regular tree of height $3$ as
shown in the following Figure 2.

Figure 2: Tree $T^{2}_{4,3,4}$ and its vertex ordering.

Note that a tree $T^{2}_{4,3,4}$ has $4$ levels, $|L_{0}|=2$, $|L_{1}|=6$,
$|L_{2}|=12$, $|L_{3}|=36$ and the vertex degrees are $m_{0}=4$, $m_{1}=3$,
$m_{2}=4$, $m_{3}=1$. Then we have $\frac{|L_{3}|}{|L_{2}|}=3$,
$\frac{|L_{2}|}{|L_{1}|}=2$ and $\frac{|L_{1}|}{|L_{0}|}=3$. Moreover, for
$j=1,2,3$, the matrices $C_{j}$ are

$C_{1}=\begin{bmatrix}\frac{1}{2}\\\\[5.69046pt] \frac{1}{2}\\\\[5.69046pt]
\frac{1}{2}\end{bmatrix}_{3\times
1},C_{2}=\begin{bmatrix}\frac{1}{2\sqrt{3}}\\\\[5.69046pt]
\frac{1}{2\sqrt{3}}\end{bmatrix}_{2\times 1}\mbox{ and
}C_{3}=\begin{bmatrix}\frac{1}{2\sqrt{3}}\\\\[2.84544pt]
\frac{1}{2\sqrt{3}}\\\\[2.84544pt] \frac{1}{2\sqrt{3}}\end{bmatrix}_{3\times
1}.$

Hence,

$B_{1}={\rm
diag}[C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1},C_{1}]$
$B_{2}={\rm diag}[C_{2},C_{2},C_{2},C_{2},C_{2},C_{2}]$ $B_{3}={\rm
diag}[C_{3},C_{3}]$

and let

$\Omega=\begin{bmatrix}0&\frac{1}{4}\\\ \frac{1}{4}&0\end{bmatrix}.$

The Randić matrix of the tree $T^{2}_{4,3,4}$ is

$\mbox{{R}}(T^{2})=\begin{bmatrix}0&B_{1}&0&0\\\ B_{1}^{T}&0&B_{2}&0\\\
0&B_{2}^{T}&0&B_{3}\\\ 0&0&B_{3}^{T}&\Omega\end{bmatrix}.$

In general, the Randić matrix of level-wise regular tree
$T^{z}=T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ of order $n$ is given by

$\mbox{{R}}(T^{z})=\begin{bmatrix}0&B_{1}&0&\cdots&\cdots&0\\\
B_{1}^{T}&0&B_{2}&\ddots&&\vdots\\\ 0&B_{2}^{T}&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&B_{h-1}&0\\\ \vdots&&\ddots&B_{h-1}^{T}&0&B_{h}\\\
0&\cdots&\cdots&0&B_{h}^{T}&\Omega\end{bmatrix},$

where

$\Omega=\left\\{\begin{array}[]{ll}0,&\mbox{ if $z=1$},\\\\[5.69046pt]
\begin{bmatrix}0&\frac{1}{m_{0}}\\\ \frac{1}{m_{0}}&0\end{bmatrix},&\mbox{ if
$z=2$}.\end{array}\right.$

We recall some well known results (refer [4] and [21]) which are useful to
prove our main results.

######  Theorem 2.4 (Eigenvalue Interlacing Theorem).

(refer [4]) Suppose $A\in\mathbb{R}^{n\times n}$ is symmetric. Let
$B\in\mathbb{R}^{m\times m}$ with $m<n$ be a principal submatrix (obtained by
deleting both $i$-th row and $i$-th column for some value of $i$). Suppose $A$
has eigenvalues $\lambda_{1}\leq\ldots\leq\lambda_{n}$ and $B$ has eigenvalues
$\lambda^{\prime}_{1}\leq\ldots\leq\lambda^{\prime}_{m}$. Then

$\lambda_{k}\leq\lambda^{\prime}_{k}\leq\lambda_{k+n-m}\mbox{ for
}k=1,2,\ldots,m.$

And if $m=n-1$ then

$\lambda_{1}\leq\lambda^{\prime}_{1}\leq\lambda_{2}\leq\lambda^{\prime}_{2}\leq\ldots\leq\lambda^{\prime}_{n-1}\leq\lambda_{n}.$

######  Lemma 2.5.

[21] Let

$M_{j}=\begin{bmatrix}p_{1}&q_{1}&0&\cdots&\cdots&0\\\
q_{1}&p_{2}&q_{2}&\ddots&&\vdots\\\ 0&q_{2}&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\ddots&0\\\
\vdots&&\ddots&\ddots&p_{j-1}&q_{j-1}\\\
0&\cdots&\cdots&0&q_{j-1}&p_{j}\end{bmatrix}$

and $M_{j}(\lambda)=\det(\lambda\mbox{\rm{I}}_{j}-M_{j})$. Then
$M_{j}(\lambda)$ satisfies the following three-term recursion formula

$M_{j}(\lambda)=(\lambda-p_{j})M_{j-1}(\lambda)-q^{2}_{j-1}M_{j-2}(\lambda)$

with $M_{0}(\lambda)=1$ and $M_{1}(\lambda)=\lambda-a_{1}$.

######  Lemma 2.6.

Let $T^{z}=T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ be the level-wise
regular tree, $L_{i}$’s are defined as earlier and

$D=\begin{bmatrix}-\mbox{\rm{I}}_{|L_{h}|}&0&0&\cdots&\cdots&0\\\
0&\mbox{\rm{I}}_{|L_{h-1}|}&0&\ddots&\ddots&\vdots\\\
0&0&-\mbox{\rm{I}}_{|L_{h-2}|}&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\ddots 0\\\
\vdots&\ddots&\ddots&\ddots&(-1)^{h}\mbox{\rm{I}}_{|L_{1}|}&0\\\
0&\cdots&\cdots&0&0&(-1)^{h+1}\mbox{\rm{I}}_{|L_{0}|}\end{bmatrix}$

then

$D(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{z}))D^{-1}=\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{z}).$

In particular,

$\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{z}))=\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{z})).$

###### Proof.

It is clear that $D=D^{-1}$. Computing the multiplication block wise, we have
$D(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{z}))D^{-1}$

$=\begin{bmatrix}-\mbox{\rm{I}}_{|L_{h}|}\cdot\lambda\mbox{\rm{I}}_{|L_{h}|}\cdot-\mbox{\rm{I}}_{|L_{h}|}&-\mbox{\rm{I}}_{|L_{h}|}\cdot
B_{1}\cdot\mbox{\rm{I}}_{|L_{h-1}}|&\cdots&\cdots&0\\\
\mbox{\rm{I}}_{|L_{h-1}|}\cdot
B_{1}^{T}\cdot-\mbox{\rm{I}}_{|L_{h}|}&\mbox{\rm{I}}_{|L_{h-1}|}\cdot\lambda\mbox{\rm{I}}_{|L_{h-1}|}\cdot\mbox{\rm{I}}_{|L_{h-1}|}&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
0&\cdots&\cdots&\cdots&(-1)^{h+1}\mbox{\rm{I}}_{|L_{0}|}(\lambda\mbox{\rm{I}}_{|L_{0}|}-\Omega)(-1)^{h+1}\mbox{\rm{I}}_{|L_{0}|}\end{bmatrix}$
$=\begin{bmatrix}\lambda\mbox{\rm{I}}_{|L_{h}|}&-B_{1}&0&\cdots&\cdots&0\\\
-B_{1}^{T}&\lambda\mbox{\rm{I}}_{|L_{h-1}|}&-B_{2}&\ddots&&\vdots\\\
0&-B_{2}^{T}&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&-B_{h-1}&0\\\
\vdots&&\ddots&-B_{h-1}^{T}&\lambda\mbox{\rm{I}}_{|L_{1}|}&-B_{h}\\\
0&\cdots&\cdots&0&-B_{h}^{T}&\lambda\mbox{\rm{I}}_{|L_{0}|}-\Omega\end{bmatrix}.$

= $\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{z})$. ∎

##  3 The spectrum of the Randić matrix of level-wise regular tree

We continue to use terms and notations defined in the previous sections. We
prove the following main result in this section.

######  Theorem 3.1.

Let $T^{z}=T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ be the level-wise
regular tree, $L^{i}$’s are defined as earlier and
$\psi=\\{j:j\in\\{1,2,\ldots,h\\}\mbox{ and }|L_{h-j+1}|>|L_{h-j}|\\}$. For
$j=1,2,\ldots,h$, let $P_{j}$ be the $j\times j$ principal sub matrix of the
$(h+1)\times(h+1)$ symmetric tridiagonal matrix

$P_{h+1}=\begin{bmatrix}0&\sqrt{\left(\frac{m_{h-1}-1}{m_{h}m_{h-1}}\right)}&0&\cdots&\cdots&0\\\
\sqrt{\left(\frac{m_{h-1}-1}{m_{h}m_{h-1}}\right)}&0&\sqrt{\left(\frac{m_{h-2}-1}{m_{h-1}m_{h-2}}\right)}&\ddots&&\vdots\\\
0&\sqrt{\left(\frac{m_{h-2}-1}{m_{h-1}m_{h-2}}\right)}&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\sqrt{\left(\frac{m_{1}-1}{m_{2}m_{1}}\right)}&0\\\
\vdots&&\ddots&\sqrt{\left(\frac{m_{1}-1}{m_{2}m_{1}}\right)}&0&\sqrt{\frac{1}{m_{1}}}\\\
0&\cdots&\cdots&0&\sqrt{\frac{1}{m_{1}}}&0\end{bmatrix}.$

and for $z=1,2$,

$P_{h+1}^{z}=\begin{bmatrix}0&\sqrt{\left(\frac{m_{h-1}-1}{m_{h}m_{h-1}}\right)}&0&\cdots&\cdots&0\\\
\sqrt{\left(\frac{m_{h-1}-1}{m_{h}m_{h-1}}\right)}&0&\sqrt{\left(\frac{m_{h-2}-1}{m_{h-1}m_{h-2}}\right)}&\ddots&&\vdots\\\
0&\sqrt{\left(\frac{m_{h-2}-1}{m_{h-1}m_{h-2}}\right)}&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\sqrt{\left(\frac{m_{1}-1}{m_{2}m_{1}}\right)}&0\\\
\vdots&&\ddots&\sqrt{\left(\frac{m_{1}-1}{m_{2}m_{1}}\right)}&0&\sqrt{\left(\frac{m_{0}-1)}{m_{1}m_{0}}\right)}\\\
0&\cdots&\cdots&0&\sqrt{\left(\frac{m_{0}-1}{m_{1}m_{0}}\right)}&\frac{(-1)^{z}}{m_{0}}\end{bmatrix}.$

Then

  1. (a)

$\sigma(\mbox{{R}}(T^{1}))=\left(\displaystyle\bigcup_{j\in\psi}\sigma(P_{j})\right)\cup\sigma(P_{h+1})$
and
$\sigma(\mbox{{R}}(T^{2}))=\left(\displaystyle\bigcup_{j\in\psi}\sigma(P_{j})\right)\cup\sigma(P^{1}_{h+1})\cup\sigma(P^{2}_{h+1})$.

  2. (b)

The multiplicity of each eigenvalue of the matrix $P_{j}$ as an eigenvalue of
$\mbox{{R}}(T)$ is at least $(|L_{h-j+1}|-|L_{h-j}|)$ for $j\in\psi$ and 1 for
$j=h+1$.

We first prove some important Lemmas which are useful to prove our main
results.

######  Lemma 3.2.

Let $T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ be the level-wise regular
tree and $B_{i}$’s are as defined earlier. Let

$P=\begin{bmatrix}\alpha_{1}\mbox{\rm{I}}_{|L_{h}|}&B_{1}&0&\cdots&\cdots&\cdots&0\\\
B_{1}^{T}&\alpha_{2}\mbox{\rm{I}}_{|L_{h-1}|}&B_{2}&\ddots&&\vdots&&\\\
0&B_{2}^{T}&&&\ddots&&&\\\ \vdots&\ddots&&&&\ddots&&&\\\
\vdots&&\ddots&&\alpha_{h-1}\mbox{\rm{I}}_{|L_{2}|}&B_{h-1}&0\\\
\vdots&&&\ddots&B_{h-1}^{T}&\alpha_{h}\mbox{\rm{I}}_{|L_{1}|}&B_{h}\\\
0&\cdots&\cdots&\cdots&0&B_{h}^{T}&\Omega^{\prime}\end{bmatrix},$

where

$\Omega^{\prime}=\left\\{\begin{array}[]{ll}\alpha_{h+1},&\mbox{ if
$z=1$},\\\\[5.69046pt] \begin{bmatrix}\alpha_{h+1}&\frac{1}{m_{0}}\\\
\frac{1}{m_{0}}&\alpha_{h+1}\end{bmatrix},&\mbox{ if
$z=2$}.\end{array}\right.$

Let $\beta_{1}=\alpha_{1}$ and
$\beta_{j}=\alpha_{j}-\frac{|L_{h-j+2}|}{|L_{h-j+1}|}\frac{1}{(m_{h-j+1}m_{h-j+2})\beta_{j-1}},j=2,3,\dots,h+1$.
If $\beta_{j}\neq 0$ for all $j=1,2,\dots,h$ and

$\beta_{h+1}\neq\left\\{\begin{array}[]{ll}0,&\mbox{ if $z=1$},\\\\[5.69046pt]
\pm\frac{1}{m_{0}},&\mbox{ if $z=2$}.\end{array}\right.$

Then

$\det
P=\left\\{\begin{array}[]{ll}\beta_{1}^{|L_{h}|}\beta_{2}^{|L_{h-1}|}\cdots\beta_{h-1}^{|L_{2}|}\beta_{h}^{|L_{1}|}\beta_{h+1},&\mbox{
if $z=1$},\\\\[5.69046pt]
\beta_{1}^{|L_{h}|}\beta_{2}^{|L_{h-1}|}\cdots\beta_{h-1}^{|L_{2}|}\beta_{h}^{|L_{1}|}\left(\beta_{h+1}+\frac{1}{m_{0}}\right)\left(\beta_{h+1}-\frac{1}{m_{0}}\right),&\mbox{
if $z=2$}.\end{array}\right.$ (2)

###### Proof.

Suppose $\beta_{j}\neq 0$ for all $j=1,2,\dots,h+1$. We apply Gauss
elimination procedure to reduce the matrix $P$ to an upper triangular matrix
without row interchanges. Then by Observation 2.1, we have the following
matrix just before the last step.

$\begin{bmatrix}\beta_{1}\mbox{\rm{I}}_{|L_{h}|}&B_{1}&0&\cdots&\cdots&\cdots&0\\\
0&\beta_{2}\mbox{\rm{I}}_{|L_{h-1}|}&B_{2}&\ddots&&&\vdots\\\
0&0&&&\ddots&&\vdots\\\ \vdots&\ddots&&&&\ddots&\vdots\\\
\vdots&&\ddots&&\beta_{h-1}\mbox{\rm{I}}_{|L_{2}|}&B_{h-1}&0\\\
\vdots&&&\ddots&0&\beta_{h}\mbox{\rm{I}}_{|L_{1}|}&B_{h}\\\
0&\cdots&\cdots&\cdots&0&B_{h}^{T}&\Omega^{\prime}\end{bmatrix}$

We now consider the following two cases.

Case-1: $z=1$ (or $T^{1}_{m_{0},m_{1},\ldots,m_{h-1}}$).

In this cases, note that $\Omega^{\prime}=\alpha_{h+1}$ and hence applying the
final step of Gauss elimination gives

$\begin{bmatrix}\beta_{1}\mbox{\rm{I}}_{|L_{h}|}&B_{1}&0&\cdots&\cdots&\cdots&0\\\
0&\beta_{2}\mbox{\rm{I}}_{|L_{h-1}|}&B_{2}&\ddots&&&\vdots\\\
0&0&&&\ddots&&\vdots\\\ \vdots&\ddots&&&&\ddots&\vdots\\\
\vdots&&\ddots&&\beta_{h-1}\mbox{\rm{I}}_{|L_{2}|}&B_{h-1}&0\\\
\vdots&&&\ddots&0&\beta_{h}\mbox{\rm{I}}_{|L_{1}|}&B_{h}\\\
0&\cdots&\cdots&\cdots&0&0&\alpha_{h+1}-|L_{1}|\frac{1}{(m_{1}m_{0})\beta_{h}}\end{bmatrix}$

Taking determinant of the above matrix, we obtain

$\det
P=\beta_{1}^{|L_{h}|}\beta_{2}^{|L_{h-1}|}\ldots\beta_{h-1}^{|L_{2}|}\beta_{h}^{|L_{1}|}\beta_{h+1}.$

Case-2: $z=2$ (or $T^{2}_{m_{0},m_{1},\ldots,m_{h-1}}$).

In this case, note that
$\Omega^{\prime}=\begin{bmatrix}\alpha_{h+1}&\frac{1}{m_{0}}\\\
\frac{1}{m_{0}}&\alpha_{h+1}\end{bmatrix}$ and hence applying the final step
of Gauss elimination gives

$\begin{bmatrix}\beta_{1}\mbox{\rm{I}}_{|L_{h}|}&B_{1}&0&\cdots&\cdots&\cdots&0\\\
0&\beta_{2}\mbox{\rm{I}}_{|L_{h-1}|}&B_{2}&\ddots&&&\vdots\\\
0&0&&&\ddots&&\vdots\\\ \vdots&\ddots&&&&\ddots&\vdots\\\
\vdots&&\ddots&&\beta_{h-1}\mbox{\rm{I}}_{|L_{2}|}&B_{h-1}&0\\\
\vdots&&&\ddots&0&\beta_{h}\mbox{\rm{I}}_{|L_{1}|}&B_{h}\\\
0&\cdots&\cdots&\cdots&0&0&\Omega^{\prime}-\frac{1}{\beta_{h}}B^{T}_{h}B_{h}\end{bmatrix}.$

Taking determinant of the above matrix, we obtain

$\det
P=\beta_{1}^{|L_{h}|}\beta_{2}^{|L_{h-1}|}\ldots\beta_{h-1}^{|L_{2}|}\beta_{h}^{|L_{1}|}\det\left(\Omega^{\prime}-\frac{1}{\beta_{h}}B^{T}_{h}B_{h}\right).$

Observe that
$\Omega^{\prime}-\frac{1}{\beta_{h}}B^{T}_{h}B_{h}=\begin{bmatrix}\alpha_{h+1}&\frac{1}{m_{0}}\\\
\frac{1}{m_{0}}&\alpha_{h+1}\end{bmatrix}-\frac{1}{\beta_{h}}\begin{bmatrix}\frac{|L_{1}|}{|L_{0}|}\frac{1}{m_{1}m_{0}}&0\\\
0&\frac{|L_{1}|}{|L_{0}|}\frac{1}{m_{1}m_{0}}\end{bmatrix}=\begin{bmatrix}\beta_{h+1}&\frac{1}{m_{0}}\\\
\frac{1}{m_{0}}&\beta_{h+1}\end{bmatrix}$. Hence,
$\det(\Omega^{\prime}-\frac{1}{\beta_{h}}B^{T}_{h}B_{h})=\beta^{2}_{h+1}-\frac{1}{m^{2}_{0}}=\left(\beta_{h+1}-\frac{1}{m_{0}}\right)\left(\beta_{h+1}+\frac{1}{m_{0}}\right)$.
Substituting this in above, we get the result. ∎

Denote $[1,h]=\\{1,2,3,\ldots,h\\}$. Define a subset $\psi$ of $[1,h]$ as
$\psi=\\{j\in[1,h]:|L_{h-j+1}|>|L_{h-j}|\\}$. Since $|L_{1}|>|L_{0}|=1$, the
index $h\in\psi$ and hence $\psi\neq\emptyset$. Observe that if
$l\in[1,h]\setminus\psi$ then $|L_{h-l+1}|=|L_{h-l}|$ and in this case,
$C_{l}$ is of size $1\times 1$ and by the definition of $B_{j}$, we have

$B_{l}=\begin{bmatrix}C_{l}&0&\cdots&0\\\ 0&C_{l}&&\vdots\\\
\vdots&&\ddots&0\\\ 0&\cdots&0&C_{l}\end{bmatrix},$

where $B_{l}$ is of size $|L_{h-l}|\times|L_{h-l}|$. That is,
$B_{l}=\frac{1}{\sqrt{(m_{h-l}m_{h-l+1})}}\mbox{\rm{I}}_{|L_{h-l}|}$.

######  Lemma 3.3.

Let $T^{z}=T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ and for
$i=0,1,\ldots,h$, $L_{i}$’s are defined as earlier. Let

$\phi_{0}(\lambda)=1,\phi_{1}(\lambda)=\lambda$

and for $j=2,3,\ldots,h+1$,

$\phi_{j}(\lambda)=\lambda\phi_{j-1}(\lambda)-\frac{|L_{h-j+2}|}{|L_{h-j+1}|(m_{h-j+2}m_{h-j+1})}\phi_{j-2}(\lambda).$
(3)

Then

  1. (a)

If $\phi_{j}(\lambda)\neq 0$ for all $j=1,2,\dots,h$ and
$\phi_{h+1}(\lambda)\neq 0$ if $z=1$ and
$\phi_{h+1}(\lambda)\neq\pm\frac{1}{m_{0}}$ if $z=2$. Then
$\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{z}))$

$=\left\\{\begin{array}[]{ll}\phi_{h+1}(\lambda)\displaystyle\prod_{j\in\psi}\phi_{j}^{|L_{h-j+1}|-|L_{h-j}|}(\lambda),&\mbox{if
$z=1$},\\\\[5.69046pt]
\left(\phi_{h+1}(\lambda)-\frac{1}{m_{0}}\phi_{h}(\lambda)\right)\left(\phi_{h+1}(\lambda)+\frac{1}{m_{0}}\phi_{h}(\lambda)\right)\displaystyle\prod_{j\in\psi}\phi_{j}^{|L_{h-j+1}|-|L_{h-j}|}(\lambda),&\mbox{if
$z=2$}.\end{array}\right.$ (4)

  2. (b)

$\sigma(R(T^{z}))=\left\\{\begin{array}[]{ll}\left(\displaystyle\bigcup_{j\in\psi}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\\}\right)\bigcup\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)=0\\},&\mbox{if
$z=1$},\\\\[22.76228pt]
\left(\displaystyle\bigcup_{j\in\psi}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\\}\right)\bigcup\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)=0\\},&\mbox{if
$z=2$}.\end{array}\right.$

###### Proof.

(a) We apply Lemma 3.2 to the matrix
$P=\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{z})$. For this matrix
$\alpha_{j}=\lambda$ for $j=1,2,3,\ldots,h+1$. Let
$\beta_{1},\beta_{2},\ldots,\beta_{h+1}$ be as in the Lemma 3.2. Suppose that
$\lambda\in\mathbb{R}$ is such that $\phi_{j}(\lambda)\neq 0$ for all
$j=1,2,\dots,h+1$. We have

$\displaystyle\beta_{1}$ $\displaystyle=$
$\displaystyle\lambda=\frac{\phi_{1}(\lambda)}{\phi_{0}(\lambda)}$
$\displaystyle\beta_{2}$ $\displaystyle=$
$\displaystyle\lambda-\frac{|L_{h}|}{|L_{h-1}|(m_{h-1}m_{h})}\frac{1}{\beta_{1}}=\lambda-\frac{|L_{h}|}{|L_{h-1}|(m_{h-1}m_{h})}\frac{\phi_{0}(\lambda)}{\phi_{1}(\lambda)}$
$\displaystyle=$
$\displaystyle\frac{\lambda\phi_{1}(\lambda)-\frac{|L_{h}|}{|L_{h-1}|(m_{h-1}m_{h})}\phi_{0}(\lambda)}{\phi_{1}(\lambda)}=\frac{\phi_{2}(\lambda)}{\phi_{1}(\lambda)}\neq
0$ $\displaystyle\beta_{3}$ $\displaystyle=$
$\displaystyle\lambda-\frac{|L_{h-1}|}{|L_{h-2}|(m_{h-2}m_{h-1})}\frac{1}{\beta_{2}}=\lambda-\frac{|L_{h-1}|}{|L_{h-2}|(m_{h-2}m_{h-1})}\frac{\phi_{1}(\lambda)}{\phi_{2}(\lambda)}$
$\displaystyle=$
$\displaystyle\frac{\lambda\phi_{2}(\lambda)-\frac{|L_{h-1}|}{|L_{h-2}|(m_{h-2}m_{h-1})}\phi_{1}(\lambda)}{\phi_{2}(\lambda)}=\frac{\phi_{3}(\lambda)}{\phi_{2}(\lambda)}\neq
0$ $\displaystyle\vdots$ $\displaystyle\vdots$ $\displaystyle\beta_{h}$
$\displaystyle=$
$\displaystyle\lambda-\frac{|L_{2}|}{|L_{1}|(m_{2}m_{1})}\frac{1}{\beta_{h-1}}=\lambda-\frac{|L_{2}|}{|L_{1}|(m_{2}m_{1})}\frac{\phi_{h-2}(\lambda)}{\phi_{h-1}(\lambda)}$
$\displaystyle=$
$\displaystyle\frac{\lambda\phi_{h-1}(\lambda)-\frac{|L_{2}|}{|L_{1}|(m_{2}m_{1})}\phi_{h-2}(\lambda)}{\phi_{h-1}(\lambda)}=\frac{\phi_{h}(\lambda)}{\phi_{h-1}(\lambda)}\neq
0$ $\displaystyle\beta_{h+1}$ $\displaystyle=$
$\displaystyle\lambda-\frac{|L_{1}|}{|L_{0}|(m_{1}m_{0})}\frac{1}{\beta_{h}}=\lambda-\frac{|L_{1}|}{|L_{0}|(m_{1}m_{0})}\frac{\phi_{h-1}(\lambda)}{\phi_{h}(\lambda)}$
$\displaystyle=$
$\displaystyle\frac{\lambda\phi_{h}(\lambda)-\frac{|L_{1}|}{|L_{0}|(m_{1}m_{0})}\phi_{h-1}(\lambda)}{\phi_{h}(\lambda)}=\frac{\phi_{h+1}(\lambda)}{\phi_{h}(\lambda)}.$

We consider the following two cases.

Case-1: $z=1$ (or $T^{1}_{m_{0},m_{1},\ldots,m_{h-1}}$).

By (2), we have

$\displaystyle\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{1}))$ $\displaystyle=$
$\displaystyle\beta_{1}^{|L_{h}|}\beta_{2}^{|L_{h-1}|}\cdots\beta_{h-1}^{|L_{2}|}\beta_{h}^{|L_{1}|}\beta_{h+1}$
$\displaystyle=$
$\displaystyle\frac{\phi_{1}^{|L_{h}|}(\lambda)}{\phi_{0}^{|L_{h}|}(\lambda)}\frac{\phi_{2}^{|L_{h-1}|}(\lambda)}{\phi_{1}^{|L_{h-1}|}(\lambda)}\frac{\phi_{3}^{|L_{h-2}|}(\lambda)}{\phi_{2}^{|L_{h-2}|}(\lambda)}\cdots\frac{\phi_{h}^{|L_{1}|}(\lambda)}{\phi_{h-1}^{|L_{1}|}(\lambda)}\frac{\phi_{h+1}(\lambda)}{\phi_{h}(\lambda)}$
$\displaystyle=$
$\displaystyle\phi_{1}^{|L_{h}|-|L_{h-1}|}(\lambda)\phi_{2}^{|L_{h-1}|-|L_{h-2}|}(\lambda)\phi_{3}^{|L_{h-2}|-|L_{h-3}|}(\lambda)\cdots\phi_{h}^{|L_{1}|-1}(\lambda)\phi_{h+1}(\lambda)$
$\displaystyle=$
$\displaystyle\phi_{h+1}(\lambda)\prod_{j\in\psi}\phi_{j}^{|L_{h-j+1}|-|L_{h-j}|}(\lambda).$

Case-2: $z=2$ (or $T^{2}_{m_{0},m_{1},\ldots,m_{h-1}}$).

By (2), we have

$\displaystyle\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{2}))$ $\displaystyle=$
$\displaystyle\beta_{1}^{|L_{h}|}\beta_{2}^{|L_{h-1}|}\cdots\beta_{h-1}^{|L_{2}|}\beta_{h}^{|L_{1}|}\left(\beta_{h+1}-\frac{1}{m_{0}}\right)\left(\beta_{h+1}+\frac{1}{m_{0}}\right)$
$\displaystyle=$
$\displaystyle\frac{\phi_{1}^{|L_{h}|}(\lambda)}{\phi_{0}^{|L_{h}|}(\lambda)}\frac{\phi_{2}^{|L_{h-1}|}(\lambda)}{\phi_{1}^{|L_{h-1}|}(\lambda)}\frac{\phi_{3}^{|L_{h-2}|}(\lambda)}{\phi_{2}^{|L_{h-2}|}(\lambda)}\cdots\frac{\phi_{h}^{|L_{1}|}(\lambda)}{\phi_{h-1}^{|L_{1}|}(\lambda)}\left(\frac{\phi_{h+1}(\lambda)}{\phi_{h}(\lambda)}-\frac{1}{m_{0}}\right)\left(\frac{\phi_{h+1}(\lambda)}{\phi_{h}(\lambda)}+\frac{1}{m_{0}}\right)$
$\displaystyle=$
$\displaystyle\phi_{1}^{|L_{h}|-|L_{h-1}|}(\lambda)\phi_{2}^{|L_{h-1}|-|L_{h-2}|}(\lambda)\phi_{3}^{|L_{h-2}|-|L_{h-3}|}(\lambda)\cdots\phi_{h}^{|L_{1}|-2}(\lambda)\cdot$
$\displaystyle\left(\phi_{h+1}(\lambda)-\frac{1}{m_{0}}\phi_{h}(\lambda)\right)\left(\phi_{h+1}(\lambda)+\frac{1}{m_{0}}\phi_{h}(\lambda)\right)$
$\displaystyle=$
$\displaystyle\left(\phi_{h+1}(\lambda)-\frac{1}{m_{0}}\phi_{h}(\lambda)\right)\left(\phi_{h+1}(\lambda)+\frac{1}{m_{0}}\phi_{h}(\lambda)\right)\displaystyle\prod_{j\in\psi}\phi_{j}^{|L_{h-j+1}|-|L_{h-j}|}(\lambda).$

(b) We consider the following two cases.

Case-1: $z=1$ (or $T^{1}=T^{1}_{m_{0},m_{1},\ldots,m_{h-1}}$).

From (4), if $\lambda\in\mathbb{R}$ is such that $\phi_{j}(\lambda)\neq 0$ for
all $j=1,2,\dots,h+1$, then $\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{1}))\neq
0$. That is,

$\bigcap_{j=1}^{h+1}\left\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)\neq
0\right\\}\subseteq(\sigma(\mbox{{R}}(T^{1})))^{c}.$

That is,

$\sigma(\mbox{{R}}(T^{1}))\subseteq\left(\bigcup_{j=1}^{h}\left\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\right\\}\right)\cup\left\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)=0\right\\}.$

We claim that

$\sigma(\mbox{{R}}(T^{1}))\subseteq\left(\bigcup_{j\in\psi}\left\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\right\\}\right)\cup\left\\{\lambda\in
R:\phi_{h+1}(\lambda)=0\right\\}.$

If $\psi=[1,h]=\\{1,2,\dots,h\\}$ then nothing to prove. Suppose that $\psi$
is proper subset of $[1,h]$ then above equation is equivalent to

$\left(\bigcap_{j\in\psi}\left\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)\neq
0\right\\}\right)\cap\left\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)\neq
0\right\\}\subseteq\left(\sigma(\mbox{{R}}(T^{1}))\right)^{c}.$

Suppose that $\lambda\in\mathbb{R}$ is such that $\phi_{j}(\lambda)\neq 0$ for
all $j\in\psi$ and $\phi_{h+1}(\lambda)\neq 0$. Since $h\in\psi$,
$\phi_{h}(\lambda)\neq 0$. If $\phi_{j}(\lambda)\neq 0$ for all
$j\in[1,h]\setminus\psi$ then
$\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{1}))\neq 0$ that is
$\lambda\in\left(\sigma(\mbox{{R}}(T^{1}))\right)^{c}$. If
$\phi_{i}(\lambda)=0$ for some $i\in[1,h]\setminus\psi$, let $l$ be the first
index in $[1,h]\setminus\psi$ such that $\phi_{l}(\lambda)=0$. Then
$\beta_{j}\neq 0$ for all $j=1,2,\dots,l-1$ and $\beta_{l}=0$. Now taking
$j=l+2$ in (3), we obtain

$\phi_{l+2}(\lambda)=\lambda\phi_{l+1}(\lambda).$ (5)

Note that $\phi_{l+1}(\lambda)\neq 0$; otherwise taking $j=l+1$ in (3), we
have

$\phi_{l+1}(\lambda)=\lambda\phi_{l}(\lambda)-\frac{|L_{h-l+1}|}{|L_{h-l}|(m_{h-l+1}m_{h-l})}\phi_{l-1}(\lambda)$

which gives $\phi_{l-1}(\lambda)=0$ as
$\phi_{l+1}(\lambda)=\phi_{l}(\lambda)=0$ and
$|L_{h-l+1}|,|L_{h-l}|,m_{h-l+1},m_{h-l}\neq 0$, and continuing this back
substitution in this way in (3) gives $\phi_{0}(\lambda)=0$, a contradiction.

Hence, $\phi_{l+1}(\lambda)\neq 0$. Therefore, we have

$\displaystyle\beta_{l+2}$ $\displaystyle=$
$\displaystyle\lambda-\frac{|L_{h-l}|}{|L_{h-l-1}|(m_{h-l}m_{h-l-1})}\frac{\phi_{l}(\lambda)}{\phi_{l+1}(\lambda)}$
$\displaystyle=$
$\displaystyle\frac{\lambda\phi_{l+1}(\lambda)-\frac{|L_{h-l}|}{|L_{h-l-1}|(m_{h-l}m_{h-l-1})}\phi_{l}(\lambda)}{\phi_{l+1}(\lambda)}$
$\displaystyle=$
$\displaystyle\frac{\phi_{l+2}(\lambda)}{\phi_{l+1}(\lambda)}$
$\displaystyle=$ $\displaystyle\lambda\hskip 56.9055pt\mbox{(by
\eqref{eq:4b}).}$

Since $l\in[1,h]-\psi$, then $|L_{h-l+1}|=|L_{h-l}|$. That means
$B_{l}=\frac{1}{\sqrt{(m_{h-l}m_{h-l+1})}}\mbox{\rm{I}}_{|L_{h-l+1}|}$ and the
Gaussian elimination procedure applied to
$P=\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{1})$ yields to the intermediate matrix

$\begin{bmatrix}\beta_{1}\mbox{\rm{I}}_{|L_{h}|}&B_{1}&0&\cdots&\cdots&\cdots&0\\\
0&\ddots&\ddots&\ddots&&&\vdots\\\
\vdots&0&0&\frac{1}{\sqrt{m_{h-l}m_{h-l+1}}}\mbox{\rm{I}}_{|L_{h-l+1}|}&0&&\vdots\\\
\vdots&\ddots&\frac{1}{\sqrt{m_{h-l}m_{h-l+1}}}\mbox{\rm{I}}_{|L_{h-l+1}|}&\lambda\mbox{\rm{I}}_{|L_{h-l}|}&B_{l+1}&\ddots&\vdots\\\
\vdots&&\ddots&B_{l+1}^{T}&\lambda\mbox{\rm{I}}_{|L_{h-l-1}|}&\ddots&0\\\
\vdots&&&\ddots&\ddots&\ddots&B_{h}\\\
0&\cdots&\cdots&\cdots&0&B_{h}^{T}&\lambda\end{bmatrix}$
$=\begin{bmatrix}\beta_{1}\mbox{\rm{I}}_{|L_{h}|}&B_{1}&0&\cdots&\cdots&\cdots&0\\\
0&\ddots&\ddots&\ddots&&&\vdots\\\
\vdots&0&0&\frac{1}{\sqrt{m_{h-l}m_{h-l+1}}}\mbox{\rm{I}}_{|L_{h-l+1}|}&0&&\vdots\\\
\vdots&\ddots&\frac{1}{\sqrt{m_{h-l}m_{h-l+1}}}\mbox{\rm{I}}_{|L_{h-l+1}|}&\beta_{l+1}\mbox{\rm{I}}_{|L_{h-l}|}&B_{l+1}&\ddots&\vdots\\\
\vdots&&\ddots&B_{l+1}^{T}&\beta_{l+2}\mbox{\rm{I}}_{|L_{h-l-1}|}&\ddots&0\\\
\vdots&&&\ddots&\ddots&\ddots&B_{h}\\\
0&\cdots&\cdots&\cdots&0&B_{h}^{T}&\beta_{h+1}\end{bmatrix}$

Now, a number of $|L_{h-l+1}|$ rows interchanges gives the matrix

$=\begin{bmatrix}\beta_{1}\mbox{\rm{I}}_{|L_{h}|}&B_{1}&0&\cdots&\cdots&\cdots&0\\\
0&\ddots&\ddots&\ddots&&&\vdots\\\
\vdots&\ddots&\frac{1}{\sqrt{m_{h-l}m_{h-l+1}}}\mbox{\rm{I}}_{|L_{h-l+1}|}&\beta_{l+1}\mbox{\rm{I}}_{|L_{h-l}|}&B_{l+1}&\ddots&\vdots\\\
\vdots&0&0&\frac{1}{\sqrt{m_{h-l}m_{h-l+1}}}\mbox{\rm{I}}_{|L_{h-l+1}|}&0&&\vdots\\\
\vdots&&\ddots&B_{l+1}^{T}&\beta_{l+2}\mbox{\rm{I}}_{|L_{h-l-1}|}&\ddots&0\\\
\vdots&&&\ddots&\ddots&\ddots&B_{h}\\\
0&\cdots&\cdots&\cdots&0&B_{h}^{T}&\beta_{h+1}\end{bmatrix}$

Therefore,

$\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{1}))=\left(\frac{-1}{m_{h-l}m_{h-l+1}}\right)^{|L_{h-l+1}|}\beta_{1}^{|L_{h}|}\beta_{2}^{|L_{h-1}|}\cdots\beta_{l-1}^{|L_{h-l+2}|}\det\begin{bmatrix}\beta_{l+2}\mbox{\rm{I}}_{|L_{h-l-1}|}&\ddots&0\\\
\ddots&\ddots&B_{h}\\\ 0&B_{h}^{T}&\beta_{l+2}\end{bmatrix}$

Now, if there exists $j\in[1,h]\setminus\psi$, $l+2\leq j\leq h-1$, such that
$\phi_{j}(\lambda)=0$, we apply the above procedure to the matrix

$\begin{bmatrix}\beta_{l+2}\mbox{\rm{I}}_{|L_{h-l-1}|}&\ddots&0\\\
\ddots&\ddots&B_{h}\\\ 0&B_{h}^{T}&\beta_{l+2}\end{bmatrix}$

Finally, we obtain ,

$\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{1}))=\gamma\cdot\beta_{h+1}=\gamma\cdot\frac{\phi_{h+1}(\lambda)}{\phi_{h}(\lambda)}$
(6)

where $\gamma$ is different from $0$ and by hypothesis,
$\phi_{h+1}(\lambda)\neq 0$ and $\phi_{h}(\lambda)\neq 0$. Therefore,

$\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{1}))\neq 0.$

That means $\lambda\in\sigma((\mbox{{R}}(T^{1}))^{c}$.

Now, we claim that

$\left(\bigcup_{j\in\psi}\left\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\right\\}\right)\cup\left\\{\lambda\in
R:\phi_{h+1}(\lambda)=0\right\\}\subseteq\sigma(\mbox{{R}}(T^{1})).$

Let
$\lambda\in\left(\displaystyle\bigcup_{j\in\psi}\left\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\right\\}\right)\cup\left\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)=0\right\\}.$
Let $l$ be the first index in $\psi$ such that $\phi_{l}(\lambda)=0.$ Then
$\beta_{l}=\frac{\phi_{l}(\lambda)}{\phi_{l-1}(\lambda)}=0.$ The corresponding
intermediate matrix in the Gaussian elimination procedure applied to the
matrix $P=\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{1})$ is

$\begin{bmatrix}\beta_{1}\mbox{\rm{I}}_{|L_{h}|}&B_{1}&0&\cdots&\cdots&0\\\
0&\ddots&\ddots&&&\vdots\\\ 0&\ddots&0&B_{l}&0&\vdots\\\
\vdots&\ddots&B_{l}^{T}&\lambda\mbox{\rm{I}}_{|L_{h-l}|}&&\vdots\\\
\vdots&&\ddots&\ddots&\ddots&B_{h}\\\ 0&\cdots&\cdots&0&B_{h}^{T}&\lambda\\\
\end{bmatrix}.$ (7)

Since $l\in\psi$, $|L_{h-l+1}|>|L_{h-l}|$ and $B_{l}$ is a matrix with more
rows than columns. Therefore, the matrix in (7) has at least two equal rows.
Thus $\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{1}))=0.$ That is,
$\lambda\in\sigma(\mbox{{R}}(T^{1})).$ Hence, we obtain

$\left(\bigcup_{j\in\psi}\left\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\right\\}\right)\subseteq\sigma(\mbox{{R}}(T^{1})).$
(8)

Now let
$\lambda\in\left\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)=0\right\\}.$
Observe that $\phi_{h}(\lambda)\neq 0$; otherwise back substitution in (3)
yields to $\phi_{0}(\lambda)=0$. If $\phi_{j}(\lambda)=0$ for some $j\in\psi$
then the use of (8) gives $\lambda\in\sigma(\mbox{{R}}(T^{1}))$. Hence
$\phi_{j}(\lambda)\neq 0$ for all $j\in\psi$. If in addition
$\phi_{j}(\lambda)\neq 0$ for all $j\in\psi\setminus[1,h]$ then (4) holds and
thus $\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T))=0$ because
$\phi_{h+1}(\lambda)=0$. Thus we obtain $\lambda\in\sigma(\mbox{{R}}(T^{1}))$.
If $\phi_{i}(\lambda)=0$ for some $i\in\psi\setminus[1,h]$ then we have the
assumptions under which (6) was obtained gives

$\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{1}))=\gamma\cdot\beta_{h+1}=\gamma\cdot\frac{\phi_{h+1}(\lambda)}{\phi_{h}(\lambda)}=0.$

Since
$\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{1}))=\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{1}))$
by Lemma 2.6, we obtain $\lambda\in\sigma(\mbox{{R}}(T^{1}))$.

Case-2: $z=2$ (or $T^{2}=T^{2}_{m_{0},m_{1},\ldots,m_{h-1}}$).

From (4), if $\lambda\in\mathbb{R}$ is such that $\phi_{j}(\lambda)\neq 0$ for
all $j=1,2,\ldots,h$ and
$\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)\neq 0$ then
$\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{2}))\neq 0$. That is,

$\left(\displaystyle\bigcap_{j=1}^{h}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)\neq
0\\}\right)\cap\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)\neq
0\\}\subseteq(\sigma(\mbox{{R}}(T^{2})))^{c}.$

That is,

$\sigma(\mbox{{R}}(T^{2}))\subseteq\left(\bigcup_{j=1}^{h}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\\}\right)\cup\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)=0\\}.$

We claim that

$\sigma(\mbox{{R}}(T^{2}))\subseteq\left(\bigcup_{j\in\psi}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\\}\right)\cup\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)=0\\}.$

Obviously, if $\psi=[1,h]=\\{1,2,\ldots,h\\}$ then the claim is straight
forward. Suppose that $\psi$ is proper subset of $[1,h]$ then above equation
is equivalent to

$\left(\bigcap_{j\in\psi}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)\neq
0\\}\right)\cap\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)\neq
0\\}\subseteq(\sigma(\mbox{{R}}(T^{2})))^{c}.$

Suppose that $\lambda\in\mathbb{R}$ is such that $\phi_{j}(\lambda)\neq 0$ for
all $j\in\psi$ and $\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)\neq
0$. Since $h\in\psi$, $\phi_{h}(\lambda)\neq 0$. If $\phi_{i}(\lambda)=0$ for
some $i\in[1,h]\setminus\psi$ then let $l$ be the first index in
$[1,h]\setminus\psi$ such that $\phi_{l}(\lambda)=0$. Then $\beta_{j}\neq 0$
for all $j=1,2,\ldots,l-1$ and $\beta_{l}=0$. Now proceeding as in case-1, we
obtain

$\displaystyle\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{2}))$ $\displaystyle=$
$\displaystyle\gamma\cdot\det\begin{bmatrix}\beta_{h+1}&\frac{1}{m_{0}}\\\
\frac{1}{m_{0}}&\beta_{h+1}\end{bmatrix}$ (9) $\displaystyle=$
$\displaystyle\gamma\cdot\left(\beta_{h+1}-\frac{1}{m_{0}}\right)\left(\beta_{h+1}+\frac{1}{m_{0}}\right)$
$\displaystyle=$
$\displaystyle\gamma\cdot\left(\frac{\phi_{h+1}(\lambda)}{\phi_{h}(\lambda)}-\frac{1}{m_{0}}\right)\left(\frac{\phi_{h+1}(\lambda)}{\phi_{h}(\lambda)}+\frac{1}{m_{0}}\right)$
$\displaystyle=$
$\displaystyle\gamma\cdot\frac{\left(\phi_{h+1}(\lambda)-\frac{1}{m_{0}}\phi_{h}(\lambda)\right)\left(\phi_{h+1}(\lambda)+\frac{1}{m_{0}}\phi_{h}(\lambda)\right)}{\phi_{h}^{2}(\lambda)}$

where $\gamma$ is different from $0$ and by hypothesis,
$\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)\neq 0$ and
$\phi_{h}(\lambda)\neq 0$. Therefore,
$\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{2}))\neq 0$. That is,
$\lambda\in(\sigma(\mbox{{R}}(T^{2})))$.

Now we claim that

$\left(\bigcup_{j\in\psi}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\\}\right)\cup\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)=0\\}\subseteq\sigma(\mbox{{R}}(T^{2})).$

Let
$\lambda\in\left(\displaystyle\bigcup_{j\in\psi}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\\}\right)$.
Let $l$ be the first index in $\psi$ such that $\phi_{l}(\lambda)=0$. Then
$\beta_{l}=\frac{\phi_{h}(\lambda)}{\phi_{h+1}(\lambda)}=0$. Again proceeding
as in case-1, we obtain

$\left(\bigcup_{j\in\psi}\\{\lambda\in\mathbb{R}:\phi_{j}(\lambda)=0\\}\right)\subseteq\sigma(\mbox{{R}}(T^{2})).$
(10)

Now let
$\lambda\in\\{\lambda\in\mathbb{R}:\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)=0\\}$.
Observe that $\phi_{h}(\lambda)\neq 0$; otherwise back substitution in (3)
yields to $\phi_{0}(\lambda)=0$, a contradiction. If $\phi_{j}(\lambda)=0$ for
some $j\in\psi$ then the use of (10) gives
$\lambda\in\sigma(\mbox{{R}}(T^{2}))$. Hence, assume $\phi_{j}(\lambda)\neq 0$
for all $j\in\psi$. If in addition $\phi_{j}(\lambda)\neq 0$ for all
$j\in\psi\setminus[1,h]$ then (4) holds and thus
$\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{2}))=0$ because
$\phi_{h+1}(\lambda)\pm\frac{1}{m_{0}}\phi_{h}(\lambda)=0$. Thus we obtain
$\lambda\in\sigma(\mbox{{R}}(T^{2}))$. If $\phi_{i}(\lambda)=0$ for some
$i\in\psi\setminus[1,h]$ then we have the assumption under which (9) was
obtain gives

$\displaystyle\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{2}))$ $\displaystyle=$
$\displaystyle\gamma\cdot\frac{\left(\phi_{h+1}(\lambda)-\frac{1}{m_{0}}\phi_{h}(\lambda)\right)\left(\phi_{h+1}(\lambda)+\frac{1}{m_{0}}\phi_{h}(\lambda)\right)}{\phi_{h}^{2}(\lambda)}=0.$

Since
$\det(\lambda\mbox{\rm{I}}-\mbox{{R}}(T^{2}))=\det(\lambda\mbox{\rm{I}}+\mbox{{R}}(T^{2}))$
by Lemma 2.6, we have $\lambda\in\sigma(\mbox{{R}}(T^{2}))$. The proof is
complete. ∎

######  Lemma 3.4.

For $j=1,2,3,\dots,h$, let $P_{j}$ be the $j\times j$ principal sub matrix of
the $(h+1)\times(h+1)$ symmetric tridiagonal matrix

$P_{h+1}=\begin{bmatrix}0&\sqrt{\left(\frac{m_{h-1}-1}{m_{h}m_{h-1}}\right)}&0&\cdots&\cdots&0\\\
\sqrt{\left(\frac{m_{h-1}-1}{m_{h}m_{h-1}}\right)}&0&\sqrt{\left(\frac{m_{h-2}-1}{m_{h-1}m_{h-2}}\right)}&\ddots&&\vdots\\\
0&\sqrt{\left(\frac{m_{h-2}-1}{m_{h-1}m_{h-2}}\right)}&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\sqrt{\left(\frac{m_{1}-1}{m_{2}m_{1}}\right)}&0\\\
\vdots&&\ddots&\sqrt{\left(\frac{m_{1}-1}{m_{2}m_{1}}\right)}&0&\sqrt{\frac{1}{m_{1}}}\\\
0&\cdots&\cdots&0&\sqrt{\frac{1}{m_{1}}}&0\end{bmatrix}.$

and for $z=1,2$,

$P_{h+1}^{z}=\begin{bmatrix}0&\sqrt{\left(\frac{m_{h-1}-1}{m_{h}m_{h-1}}\right)}&0&\cdots&\cdots&0\\\
\sqrt{\left(\frac{m_{h-1}-1}{m_{h}m_{h-1}}\right)}&0&\sqrt{\left(\frac{m_{h-2}-1}{m_{h-1}m_{h-2}}\right)}&\ddots&&\vdots\\\
0&\sqrt{\left(\frac{m_{h-2}-1}{m_{h-1}m_{h-2}}\right)}&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\sqrt{\left(\frac{m_{1}-1}{m_{2}m_{1}}\right)}&0\\\
\vdots&&\ddots&\sqrt{\left(\frac{m_{1}-1}{m_{2}m_{1}}\right)}&0&\sqrt{\left(\frac{m_{0}-1)}{m_{1}m_{0}}\right)}\\\
0&\cdots&\cdots&0&\sqrt{\left(\frac{m_{0}-1}{m_{1}m_{0}}\right)}&\frac{(-1)^{z}}{m_{0}}\end{bmatrix},$

and $\phi_{j}(\lambda),j=1,2,\ldots,h+1$ are as defined in Lemma 3.3. Then for
$j=1,2,\ldots,h+1$,

$\det(\lambda\mbox{\rm{I}}-P_{j})=\phi_{j}(\lambda).$

and for $z=1,2$,

$\det(\lambda\mbox{\rm{I}}-P^{z}_{h+1})=\phi_{h+1}(\lambda)+\frac{(-1)^{z}}{m_{0}}\phi_{h}(\lambda).$

###### Proof.

In Lemma 2.5, taking $p_{j}=0$ for $j=1,2,3,\dots,h$ and $p_{h+1}=0$ for
$P_{h+1}$ and $p_{h+1}=\frac{(-1)^{z}}{m_{0}}$ for $P^{z}_{h+1}$ (where
$z=1,2$), $q_{j}=\sqrt{\frac{|L_{h-j+1}|}{(m_{h-j+1}m_{h-j})|L_{h-j}|}}$ and
in addition, using
$\sqrt{\frac{|L_{h-j+1}|}{(m_{h-j+1}m_{h-j})|L_{h-j}|}}=\sqrt{\frac{m_{h-j}-1}{m_{h-j+1}m_{h-j}}}$
for $j=1,2,\dots,h$ and if $T^{1}=T^{1}_{m_{0},m_{1},\ldots,m_{h-1}}$ then
observe that
$\sqrt{\frac{|L_{1}|}{(m_{0}m_{1})|L_{0}|}}=\sqrt{\frac{|L_{1}|}{m_{0}m_{1}}}=\sqrt{\frac{m_{0}}{m_{0}m_{1}}}=\sqrt{\frac{1}{m_{1}}}$
in (3) gives the polynomials $\phi_{j}(\lambda),\;j=1,\dots,h$ which completes
the proof. ∎

###### Proof of Theorem 3.1.

We recall that eigenvalues of any symmetric tridiagonal matrix with nonzero
co-diagonal entries are simple. Then (a) and (b) both are immediate
consequences of Lemma 3.3 and Lemma 3.4. ∎

######  Theorem 3.5.

Let $T^{z}=T^{z}_{m_{0},m_{1},\ldots,m_{h-1}}\;(z=1,2)$ be the level-wise
regular tree of order $n$ and
$\rho_{1}(T^{z})\geq\rho_{2}(T^{z})\geq\ldots\geq\rho_{n}(T^{z})$ be the
eigenvalues of $\mbox{{R}}(T^{z})\;(z=1,2)$. Then

  1. (a)

$\rho_{1}(T^{1})=1\in\sigma(P_{h+1})$ and
$\rho_{1}(T^{2})=1\in\sigma(P^{2}_{h+1}),$

  2. (b)

The multiplicity of $0$ as an eigenvalue of $\mbox{{R}}(T^{z})$ is
$\alpha+\displaystyle\sum_{j\in\psi\atop
j=odd}\left(|L_{h-j+1}|-|L_{h-j}|\right)$, where $\alpha=1$ if $h$ is even and
$0$ otherwise.

###### Proof.

(a) The proof follows by using interlacing property of the eigenvalues of real
symmetric matrix in Theorem 3.1 and observing that
$\sigma(P^{1}_{h+1})=-\sigma(P^{2}_{h+1})$.

(b) Again the proof is straight forward by using the fact that
$\mbox{{R}}(T^{z})\;(z=1,2)$ is a real symmetric matrix (hence the eigenvalues
are real) and $T^{z}\;(z=1,2)$ is bipartite graph (hence
$\rho_{i}=\rho_{n-i+1}\;i=1,2,\ldots,n$) in Theorem 3.1. ∎

######  Example 3.6.

Let $T^{1}_{4,4,3}$ be the tree as in Fig. 2.2. For $T^{1}_{4,4,3}$,
$h=3,m_{3}=1,m_{2}=3,m_{1}=4,m_{0}=4,|L_{3}|=24,|L_{2}|=12,|L_{1}|=4,|L_{0}|=1$.

Hence, we have $P_{4}=\begin{bmatrix}0&\sqrt{\left(\frac{2}{3}\right)}&0&0\\\
\sqrt{\left(\frac{2}{3}\right)}&0&\sqrt{\left(\frac{1}{4}\right)}&0\\\
0&\sqrt{\left(\frac{1}{4}\right)}&0&\sqrt{\left(\frac{1}{4}\right)}\\\
0&0&\sqrt{\left(\frac{1}{4}\right)}&0\end{bmatrix}$

Using Theorem 3.1, the eigenvalues of Randić matrix of $T^{1}_{4,4,3}$ with
its multiplicity are given in the following table.

$\begin{array}[]{|l|l|l|}\hline\cr{\rm Matrix}&{\rm Eigenvalues}&{\rm
Multiplicity}\\\ \hline\cr\hline\cr
P_{1}&0&(|L_{3}|-|L_{2}|)=24-12=12\\\\[8.5359pt]
P_{2}&-\frac{\sqrt{6}}{3},\frac{\sqrt{6}}{3}&(|L_{2}|-|L_{1}|)=12-4=8\\\\[8.5359pt]
P_{3}&-\frac{\sqrt{33}}{6},0,\frac{\sqrt{33}}{6}&(|L_{1}|-|L_{0}|)=4-1=3\\\\[8.5359pt]
P_{4}&-\frac{1}{\sqrt{6}},-1,1,\frac{1}{\sqrt{6}}&1\\\\[8.5359pt]
\hline\cr\end{array}$

######  Example 3.7.

Let $T^{2}_{4,3,4}$ be the tree as in Fig. 2.3. For $T^{2}_{4,3,4}$, $h=3$,
$m_{3}=1,m_{2}=4,m_{1}=3,m_{0}=4$ and
$|L_{3}|=36,|L_{2}|=12,|L_{1}|=6,|L_{0}|=2$.

Hence, for $z=1,2$, we have
$P_{4}^{z}=\begin{bmatrix}0&\sqrt{\left(\frac{3}{4}\right)}&0&0\\\
\sqrt{\left(\frac{3}{4}\right)}&0&\sqrt{\left(\frac{1}{6}\right)}&0\\\
0&\sqrt{\left(\frac{1}{6}\right)}&0&\sqrt{\left(\frac{1}{4}\right)}\\\
0&0&\sqrt{\left(\frac{1}{4}\right)}&\frac{(-1)^{z}}{4}\end{bmatrix}$

Using Theorem 3.1, the eigenvalues of Randić matrix of $T^{2}_{4,3,4}$ with
its multiplicity are given in the following table.

$\begin{array}[]{|l|l|l|}\hline\cr{\rm Matrix}&{\rm Eigenvalues}&{\rm
Multiplicity}\\\ \hline\cr\hline\cr
P_{1}&0&\left(|L_{3}|-|L_{2}|\right)=36-12=24\\\\[8.5359pt]
P_{2}&-\frac{\sqrt{3}}{2},\frac{\sqrt{3}}{2}&\left(|L_{2}|-|L_{1}|\right)=12-6=6\\\\[8.5359pt]
P_{3}&-\frac{\sqrt{33}}{6},0,\frac{\sqrt{33}}{6}&(|L_{1}|-|L_{0}|)=6-2=4\\\\[8.5359pt]
P^{1}_{4}&-1,-0.5672,0.3373,0.9799&1\\\\[8.5359pt]
P^{2}_{4}&-0.9799,-0.3373,0.5672,1&1\\\ \hline\cr\end{array}$

The star $K_{1,n-1}$ is a level-wise regular trees $T^{1}_{n-1,1}$. The Randić
spectra of $K_{1,n-1}$ is given in [1] as follows:

######  Theorem 3.8.

[1] Let $K_{1,n-1}$ be the star on $n$ vertices. Then
$S_{R}(K_{1,n-1})=\bigg{(}\begin{matrix}-1&0&1\\\
1&n-2&1\end{matrix}\bigg{)}$.

The above result can also be proved using our main result Theorem 3.1. The
outline of the proof is as follows: For a star graph $K_{1,n-1}$ on $n$
vertices, note that $h=1$.

Hence, we have $P_{2}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}.$

Using Theorem 3.1, the Randić spectra of $K_{1,n-1}$ is given as

$\begin{array}[]{|l|l|l|}\hline\cr{\rm Matrix}&{\rm Eigenvalues}&{\rm
Multiplicity}\\\ \hline\cr\hline\cr
P_{1}&0&(|L_{1}|-|L_{0}|)=(n-1)-1=n-2\\\\[8.5359pt] P_{2}&-1,1&1\\\
\hline\cr\end{array}$

## Concluding Remarks

The results presented in this paper reduce the computation of the eigenvalues
of the Randić matrix of level-wise regular trees of size equal to the order
(given in (1)) of level-wise regular trees to specific tridiagonal matrices
(described in Theorem 3.1) of size equal to the height of level-wise regular
trees plus one. For examples, the level-wise regular trees given in Examples
2.2 and 2.3 are of order 41 and 56, respectively (and hence their Randić
matrices of size $41\times 41$ and $56\times 56$, respectively), but the
eigenvalues for both trees can be calculated using matrices of size $4\times
4$ (refer Examples 3.6 and 3.7). Hence, the Randić index (which is the sum of
the squares of the eigenvalues of Randić matrix) and the Randić energy (which
is the sum of the absolute values of the eigenvalues of Randić matrix) can be
easily calculated for level-wise regular trees.

## References

  * [1] S. Alikhani and N. Ghambari, Randić energy of specific graphs, Applied Math. and Compu., 269 (2015), 722–730.
  * [2] E. Andrade, H. Gomes, M. Robbiano, Spectra and Randić spectra of caterpillar graphs and applications to the energy, MATCH Commun. Math. Comput. Chem., 77 (2017), 61–75.
  * [3] S. B. Bozkurt, A. D. Güngör, I. Gutman, A. S. Cevik, Randić Matrix and Randić Energy, MATCH Commun. Math. Comput. Chem., 64 (2010), 239–250.
  * [4] D. M. Cvetković, M. Doob and H. Sachs, Spectra of graphs - theory and application, Academic Press, New York, 1980.
  * [5] M. Dehmer, M. Moosbrugger, Y. Shi, Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix, Applied Math. and Compu., 268 (2015), 164–168.
  * [6] R. Fernandes, H. Gomes, E. A. Martins, On the spectra of some graphs like weighted rooted trees, Linear Algebra and Appl., 428 (2008), 2654–2674.
  * [7] B. Furtula, I. Gutman, Comparing energy and Randić energy, Maced. J. Chem. and Chem. Engin., 32 (2013), 117–123.
  * [8] Y. Gao, W. Gao, Y. Shao, The minimal Randić energy of trees with given diameter, Applied Math. and Compu., 411 (2021), 126489.
  * [9] I. Gutman, B. Furtula (Eds.), Recent results in the theory of Randić index, Univ. Kragujevac, Kragujevac, 2008.
  * [10] I. Gutman, B. Furtula and S. B. Bozkurt, On Randić energy, Linear Algebra and Appl., 442 (2014), 50–57.
  * [11] X. Li, I. Gutman, Mathematical aspects of Randić-type molecular structure descriptors, Univ. Kragujevac, Kragujevac, 2006.
  * [12] X. Li, Y. Shi, A survey on the Randić index, MATCH Commun. Math. Comput. Chem., 59 (2008) 127–-156.
  * [13] B. Liu, Y. Huang, J. Feng, A note on the Randić spectral radius, MATCH Commun. Math. Comput. Chem., 68 (2012), 913–916.
  * [14] M. Randić, On characterization of molecular branching, J. Amer. Chem. Soc. 97 (1975) 6609-–6615.
  * [15] M. Randić, On history of the Randić index and emerging hostility toward chemical graph theory, MATCH Commun. Math. Comput. Chem. 59 (2008) 5–-124.
  * [16] B. Rather, S. Pirzada, M. Bhat, T. Chishti, On Randić spectrum of zero divisor graphs of commutative ring $\mathbb{Z}_{n}$, Communications in Combi. and Opt., 8(1) (2023), 103–113.
  * [17] J. A. Rodríguez, A spectral approach to the Randić index, Linear Algebra Appl., 400 (2005), 339–344.
  * [18] J. A. Rodríguez, J. M. Sigarreta, On the Randić index and conditional parameters of a graph, MATCH Commun. Math. Comput. Chem., 54 (2005), 403–416.
  * [19] O. Rojo, The spectrum of the Laplacian matrix of a balanced binary tree, Linear Algebra Appl., 349 (2002), 203–219.
  * [20] O. Rojo and R. Soto, The spectra of the adjacency matrix and Laplacian matric for some balanced trees, Linear Algebra Appl., 403 (2005), 97–117.
  * [21] L. N. Trefethen, D. Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics, 1997.
  * [22] D. Yin, On the multiple eigenvalue of Randić matrix of trees, Linear and Multilinear Algebra, 69 (2021), 1137–1150.


# A New Approximation to the Normal Distribution Quantile Function

Paul M. Voutier

###### Abstract

We present a new approximation to the normal distribution quantile function.
It has a similar form to the approximation of Beasley and Springer [3],
providing a maximum absolute error of less than $2.5\cdot 10^{-5}$. This is
less accurate than [3], but still sufficient for many applications. However it
is faster than [3]. This is its primary benefit, which can be crucial to many
applications, including in financial markets.

##  1 Introduction

The use of the inverse of the CDF for a probability distribution, also known
as the quantile function, is widespread in statistical modelling (see, for
example, [5, 7]).

During recent work, the need arose for a fast and reasonably accurate
approximation to the normal distribution quantile function, $N^{-1}(x)$.
Accuracy similar to the approximation in Equation 26.2.23 of [1] was
sufficient (max absolute error less than $4.5\cdot 10^{-4}$). But speed was
crucial.

The approximation of Beasley and Springer [3], along with related
approximations such as Acklam’s [2], provides improvements in terms of both
accuracy and speed.

Both the Acklam and the Beasley-Springer approximations are based on the same
ideas:
(1) consider narrow tails separately from a wide central area
(2) use a rational function of $x$ to approximate $N^{-1}(x)$ in this wide
central area (avoiding expensive operations like $\log$ and sqrt)
(3) take advantage of the fact that $N^{-1}(x-1/2)$ is an odd function.

The second and third ideas suggest that for the central region, we consider
rational approximations of the form

$(x-1/2)F((x-1/2)^{2}),$

where $F$ is a rational function. The approximations of Acklam, Beasley-
Springer, and others for the central region are of this form.

The Beasley-Springer approximation for the central region is sometimes called
a $(3,4)$ scheme, since the numerator of $F$ is cubic in $(x-1/2)^{2}$ and the
denominator of $F$ is of degree $4$ in $(x-1/2)^{2}$. Similarly, the Acklam
approximation is called a $(5,5)$ scheme.

##  2 New Approximations

For increased speed, here we consider a $(2,2)$ scheme for the central region
and a $(3,2)$ scheme for the tails.

We chose the boundaries between the central region and the tails to be at
$0.0465$ and $0.9535$, since with the above schemes and boundaries the maximum
absolute error in both regions was nearly the same and both slightly less than
$2.5\cdot 10^{-5}$.

###  2.1 Central Region

####  2.1.1 $0.0465\leq p\leq 0.9535$

Put $q=p-0.5$ and let $r=q^{2}$. For $0.0465\leq p\leq 0.9535$, define

$f_{central}(p)=q\frac{\displaystyle a_{2}r^{2}+a_{1}r+a_{0}}{\displaystyle
r^{2}+b_{1}r+b_{0}}=q\left(a_{2}+\frac{\displaystyle
a_{1}^{\prime}r+a_{0}^{\prime}}{\displaystyle r^{2}+b_{1}r+b_{0}}\right)$

where

$\displaystyle a_{0}$ $\displaystyle=$ $\displaystyle 0.389422403767615,$
$\displaystyle a_{1}$ $\displaystyle=$ $\displaystyle-1.699385796345221,$
$\displaystyle a_{2}$ $\displaystyle=$ $\displaystyle 1.246899760652504,$
$\displaystyle a_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
0.195740115269792,$ $\displaystyle a_{1}^{\prime}$ $\displaystyle=$
$\displaystyle-0.652871358365296,$ $\displaystyle b_{0}$ $\displaystyle=$
$\displaystyle 0.155331081623168,$ $\displaystyle b_{1}$ $\displaystyle=$
$\displaystyle-0.839293158122257.$

The benefit of the second expression is that we save one multiplication by
using it. Similarly, normalising the denominator so that the leading
coefficient is $1$, rather than the constant coefficient as some authors do,
also saves another multiplication.

There are 12 points of maximum error (also known as alternating points) in the
interval $[0.0465,0.9535]$:

$(p,err_{abs})$ | $(p,err_{abs})$
---|---
$(0.046500,2.494327\cdot 10^{-5})$ | $(0.592289,2.494326\cdot 10^{-5})$
$(0.054264,2.494331\cdot 10^{-5})$ | $(0.752182,2.494327\cdot 10^{-5})$
$(0.081621,2.494328\cdot 10^{-5})$ | $(0.859308,2.494323\cdot 10^{-5})$
$(0.140694,2.494323\cdot 10^{-5})$ | $(0.918381,2.494328\cdot 10^{-5})$
$(0.247820,2.494327\cdot 10^{-5})$ | $(0.945738,2.494331\cdot 10^{-5})$
$(0.407712,2.494326\cdot 10^{-5})$ | $(0.945350,2.494327\cdot 10^{-5})$

From the theorems of Chebyshev and de la Vallée Poussin (see [4, Section
5.5]), it follows that $f_{central}(p)$ is essentially the best possible
rational approximation of $(2,2)$ scheme.

For comparison, the maximum absolute error of the “central” approximation in
[3] is under $1.85\cdot 10^{-9}$.

This approximation was found using the minimax function within the numapprox
package of Maple:

    Digits:=60:with(numapprox):
    uBnd:=0.4535^2:
    minimax(x->inverseCDFCentralRatApprox(x),0..uBnd,[2,2],x->sqrt(x));

where
inverseCDFCentralRatApprox(x) is the function $N^{-1}(\sqrt{x}+1/2)/\sqrt{x}$,
uBnd is the range we want the approximation over,
$[2,2]$ specifies that we want the degree of both the numerator and the
denominator to be $2$, and
$\sqrt{x}$ is the weight function we use, since we want to get the best
approximation to $N^{-1}(\sqrt{x}+1/2)$ rather than
$N^{-1}(\sqrt{x}+1/2)/\sqrt{x}$.

We tried other values of uBnd near $0.4535$, but the smallest maximum absolute
error was found with this particular value.

####  2.1.2 $0.025\leq p\leq 0.975$

The use of an even wider central region may be preferred, as this can provide
further performance gains by reducing the expensive log and sqrt operations
required for the tails.

We give one such example here (found as above using Maple, but with
uBnd=0.475).

Put $q=p-0.5$ and let $r=q^{2}$. For $0.025\leq p\leq 0.975$, define

$f_{central}(p)=q\left(a_{2}+\frac{\displaystyle a_{1}r+a_{0}}{\displaystyle
r^{2}+b_{1}r+b_{0}}\right)$

where

$\displaystyle a_{0}$ $\displaystyle=$ $\displaystyle 0.151015505647689,$
$\displaystyle a_{1}$ $\displaystyle=$ $\displaystyle-.5303572634357367,$
$\displaystyle a_{2}$ $\displaystyle=$ $\displaystyle 1.365020122861334,$
$\displaystyle b_{0}$ $\displaystyle=$ $\displaystyle 0.132089632343748,$
$\displaystyle b_{1}$ $\displaystyle=$ $\displaystyle-.7607324991323768.$

The maximum absolute error for this approximation is less than $1.16\cdot
10^{-4}$ which occurs near $p=0.9692$. While this error is much larger than
the error in the previous section, it is still well smaller than the maximum
error for the Abramowitz-Stegun approximation ($4.5\cdot 10^{-4}$).

###  2.2 Tails

####  2.2.1 $e^{-37^{2}/2}<p<0.0465$

For $5.3\ldots\cdot 10^{-298}=e^{-37^{2}/2}<p<0.0465$, put
$r=\sqrt{\log(1/p^{2})}$ and define

$f_{tail}(p)=\frac{c_{3}r^{3}+c_{2}r^{2}+c_{1}r+c_{0}}{r^{2}+d_{1}r+d_{0}}=c_{3}r+c_{2}^{\prime}+\frac{c_{1}^{\prime}r+c_{0}^{\prime}}{r^{2}+d_{1}r+d_{0}}.$

where

$\displaystyle c_{0}$ $\displaystyle=$ $\displaystyle 16.896201479841517652,$
$\displaystyle c_{1}$ $\displaystyle=$ $\displaystyle-2.793522347562718412,$
$\displaystyle c_{2}$ $\displaystyle=$ $\displaystyle-8.731478129786263127,$
$\displaystyle c_{3}$ $\displaystyle=$ $\displaystyle-1.000182518730158122,$
$\displaystyle c_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
16.682320830719986527,$ $\displaystyle c_{1}^{\prime}$ $\displaystyle=$
$\displaystyle 4.120411523939115059,$ $\displaystyle c_{2}^{\prime}$
$\displaystyle=$ $\displaystyle 0.029814187308200211,$ $\displaystyle d_{0}$
$\displaystyle=$ $\displaystyle 7.173787663925508066,$ $\displaystyle d_{1}$
$\displaystyle=$ $\displaystyle 8.759693508958633869.$

As with the “central” approximation, this approximation was also found using
the minimax function within the numapprox package of Maple:

    Digits:=60:with(numapprox):
    v:=0.0465:
    uBnd:=0.4535^2:
    minimax(y->inverseCDF(exp(-y*y/2)), sqrt(log(1/v^2))..37, [3,2]);

Note that since we are approximating $N^{-1}(x)$ itself here, we do not
include a weight function in the arguments of the minimax function and so the
default weight function $1$ is used.

The maximum absolute error in this case is less than $2.458\cdot 10^{-5}$.

####  2.2.2 $0.9535<p<1-e^{-37^{2}/2}$

Due to the symmetry of $N^{-1}(p)$ about $p=1/2$, we approximate $N^{-1}(p)$
by $-f_{tail}(1-p)$ (note that here $r=\sqrt{\log(1/(1-p)^{2})}$).

##  3 Abramowitz and Stegun Approximations

Having found the above new approximations, we turned our attention to the
approximations in Equations 26.2.22 and 26.2.23 of [1]. As those authors note,
these approximations are from [6]. In particular, Sheets 67 and 68 on pages
191–192 of [6].

If we restrict our attention to ranges like $e^{-37^{2}/2}<p<1-e^{-37^{2}/2}$
(this includes almost the entire IEEE-754 range of representable real
numbers), then we can improve on the approximations of Abramowitz and Stegun.

For example, in this range, we can replace Equation 26.2.23 of [1] with

$x_{p}=t-\frac{c_{2}t^{2}+c_{1}t+c_{0}}{d_{3}t^{3}+d_{2}t^{2}+d_{1}t+1}+\epsilon(p),$

where $|\epsilon(p)|<8\cdot 10^{-5}$ and

$\displaystyle c_{0}$ $\displaystyle=$ $\displaystyle 2.653962002601684482,$
$\displaystyle c_{1}$ $\displaystyle=$ $\displaystyle 1.561533700212080345,$
$\displaystyle c_{2}$ $\displaystyle=$ $\displaystyle 0.061146735765196993,$
$\displaystyle d_{1}$ $\displaystyle=$ $\displaystyle 1.904875182836498708,$
$\displaystyle d_{2}$ $\displaystyle=$ $\displaystyle 0.454055536444233510,$
$\displaystyle d_{3}$ $\displaystyle=$ $\displaystyle 0.009547745327068945.$

This is over five times more accurate than the approximation in [1]. However,
as one increases the range even closer to $0$ and $1$, the max absolute
increases until we obtain Equation 26.2.23 of [1]. The near-best possible
nature of Equation 26.2.23 is illustrated by the graph in Sheet 68 of [6]
showing that Chebyshev’s theorem nearly holds for this approximation.

Note also that this approximation shows the justification for the use of
$\sqrt{\log(1/p^{2})}$ in these tail approximations. As $p\rightarrow 0$,
$N^{-1}(p)$ approaches $-\sqrt{\log(1/p^{2})}$ plus a quantity that approaches
$0$ as $p$ does.

##  4 Performance

Using Java (JDK $1.6.0\\_17$), we coded the following approximations in order
to compare their performance.

$\bullet$ the Abramowitz-Stegun approximation (AS in the table below)
$\bullet$ the Beasley-Springer approximation (BS in the table below)
$\bullet$ the approximation from Section 2 using the central region
approximation in Section 2.1.1 (Rat22A in the table below)
$\bullet$ the approximation from Section 2 using the central region
approximation in Section 2.1.2 (Rat22B in the table below).

In each case, we calculated the approximation 200,000 times for each $p$ from
$0.001$ to $0.999$ with $0.001$ as our step size. These calculations were done
on a Dell Inspiron 1525, running Windows Vista and using an Intel Core 2 Duo
T5800 2.00 GHz CPU. The times in milliseconds for each approximation are given
in the table below.

method | time(ms)
---|---
AS | 25,210
BS | 10,212
Rat22A | 8052
Rat22B | 6649

As one would expect, the new approximations given here are faster than the
currently known ones. The comparison between Rat22A and Rat22B is also
interesting, as it shows the impact of the calculation of the log and sqrt
operations. Although these operations only need to be performed for a small
subset of all values of $p$, reducing the number of these operations by just
under 50% reduced the CPU time required by nearly 20%.

## References

  * [1] M. Abramowitz and I.E. Stegun (ed.), Handbook of Mathematical Functions With Formulas, Graphs and Mathematical Tables. National Bureau of Standards, Washington (1964).
  * [2] P. J. Acklam, `http://home.online.no/~pjacklam/notes/invnorm/`.
  * [3] J. D. Beasley and S. G. Springer, The percentage points of the Normal Distribution, Applied Statistics. 26 (1977), 118–121.
  * [4] E. W. Cheney, Introduction to Approximation Theory, AMS Chelsea Publishing, Providence (1982).
  * [5] W. G. Gilchrist, Statistical Modelling with Quantile Functions, Chapman & Hall, London (2000).
  * [6] C. Hastings, Approximations for Digital Computers. Princeton University Press, Princeton (1955).
  * [7] P. Jaeckel, Monte Carlo Methods in Finance. Wiley, Chichester (2002).

Paul Voutier
London, UK
<EMAIL_ADDRESS>