Overview of the Rayleigh Quotient
A brief summary of the Rayleigh quotient, which often appears in graph theory and linear algebra.
The Rayleigh quotient $R$ is defined as follows using a symmetric matrix $\mathbf{A}$ and a non-zero $n$-dimensional vector $\mathbf{x}$:
$$ R(\mathbf{x}) = \frac{\mathbf{x}^T \mathbf{A} \mathbf{x}}{\mathbf{x}^T \mathbf{x}} $$
In this article, we will explain the properties of the Rayleigh quotient and provide an implementation example in Python. The source code is also available on GitHub for reference if needed.
Source Code
GitHub
- The file in Jupyter Notebook format can be found here
Google Colaboratory
- If you want to execute it on Google Colaboratory, click here
Execution Environment
Since the operating system is macOS, please note that the options may differ from Linux or Unix commands.
!sw_vers
ProductName: macOS
ProductVersion: 13.5.1
BuildVersion: 22G90
!python -V
Python 3.9.17
Import the basic libraries and check their versions using watermark. Additionally, set the seed for random number generation.
import random
import numpy as np
seed = 123
random_state = 123
random.seed(seed)
np.random.seed(seed)
from watermark import watermark
print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))
Python implementation: CPython
Python version : 3.9.17
IPython version : 8.17.2
numpy: 1.25.2
Watermark: 2.4.3
Properties of the Rayleigh Quotient
A symmetric matrix $\mathbf{A}$ has real eigenvalues. Let $\lambda_i$ be the eigenvalues and $\mathbf{v}_i$ be the eigenvectors. Then, the Rayleigh quotient can be expressed as follows:
$$ R\left(\mathbf{x}\right)=\frac{\mathbf{x}^T \mathbf{A} \mathbf{x}}{\mathbf{x}^T \mathbf{x}} = \frac{\left(\sum_{i=1}^{n} \alpha_i \mathbf{v}_i\right)^T \mathbf{A} \left(\sum_{j=1}^{n} \alpha_j \mathbf{v}_j\right)}{\left(\sum_{k=1}^{n} \alpha_k \mathbf{v}_k\right)^T \left(\sum_{l=1}^{n} \alpha_l \mathbf{v}_l\right)} = \frac{\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j \mathbf{v}_i^T \mathbf{A} \mathbf{v}_j}{\sum_{k=1}^{n} \sum_{l=1}^{n} \alpha_k \alpha_l \mathbf{v}_k^T \mathbf{v}_l} $$
For symmetric matrices, the eigenvectors are orthogonal, so $ \mathbf{v}_i^T \mathbf{v}_j = 0 $ (when $ i \neq j $) and $ \mathbf{v}_i^T \mathbf{v}_i = 1 $.
Therefore,
$$ R\left(\mathbf{x}\right)=\frac{\sum_{i=1}^{n} \alpha_i^2 \lambda_i}{\sum_{k=1}^{n} \alpha_k^2} $$
This shows that it is a weighted average of the eigenvalues $ \lambda_i $ of matrix $ \mathbf{A} $. Also, if we choose $\mathbf{x}$ to be, for example, the eigenvector corresponding to the maximum eigenvalue, the maximum value of $ R\left(\mathbf{x}\right) $ will be the maximum eigenvalue. Conversely, if we choose the eigenvector corresponding to the minimum eigenvalue, we will obtain the minimum eigenvalue.
Solution Using Lagrange Multipliers
Referring to Wikipedia , we can use Lagrange multipliers to prove the maximum and minimum values of the Rayleigh quotient.
First, similarly to before, let’s define the Rayleigh quotient of matrix $ \mathbf{A} $ as $ R(\mathbf{x}) $.
$$ R(\mathbf{x}) = \frac{\mathbf{x}^T \mathbf{A} \mathbf{x}}{\mathbf{x}^T \mathbf{x}} $$
Also, let $ \lambda $ be the eigenvalue of matrix $ \mathbf{A} $ and $ \mathbf{v} $ be the corresponding eigenvector. Then the following holds.
$$ \mathbf{A} \mathbf{v} = \lambda \mathbf{v} $$
In Lagrange’s method of undetermined multipliers, we find the optimal solution under the constraint $ g(\mathbf{x}) = 0 $ when maximizing or minimizing the objective function $ f(\mathbf{x}) $. In the method of undetermined multipliers, it is common to introduce the Lagrange function $ L(\mathbf{x}, \lambda) $.
$$ L(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x}) $$
Here, $ \lambda $ is the Lagrange multiplier. In the case of the Rayleigh quotient, the objective function $ f(\mathbf{x}) $ is $ \mathbf{x}^T \mathbf{A} \mathbf{x} $, and the constraint $ g(\mathbf{x}) $ is $ \mathbf{x}^T \mathbf{x} - 1 = 0 $. By setting the condition that $\mathbf{x}$ has a norm of 1 as the constraint condition $ g(\mathbf{x}) $, we guarantee that $\mathbf{x}$ is a unit vector.
Let’s set up the Lagrange function as follows.
$$ L(\mathbf{x}, \lambda) = \mathbf{x}^T \mathbf{A} \mathbf{x} - \lambda (\mathbf{x}^T \mathbf{x} - 1) $$
To find the $ \mathbf{x} $ that maximizes this Lagrange function, consider the condition where the gradient equals zero.
$$ \nabla_{\mathbf{x}} L(\mathbf{x}, \lambda) = 0 $$
Solving this yields the following.
$$ 2 \mathbf{A} \mathbf{x} - 2 \lambda \mathbf{x} = 0 $$
$$ \mathbf{A} \mathbf{x} = \lambda \mathbf{x} $$
This expresses the relationship between the eigenvalue $ \lambda $ of matrix $ \mathbf{A} $ and the corresponding eigenvector $ \mathbf{x} $, showing that the maximum value of the Rayleigh quotient equals the maximum eigenvalue of $ \mathbf{A} $.
Implementation Example in Python
Here’s a simple implementation example in Python.
import numpy as np
# Generate a random symmetric matrix A and a vector x
A = np.random.rand(3, 3)
A = (A + A.T) / 2
# Prepare a random vector
x = np.random.rand(3)
# Rayleigh quotient
R = np.dot(x.T, np.dot(A, x)) / np.dot(x.T, x)
print("Rayleigh Quotient:", R.round(2))
Rayleigh Quotient: 1.47
Conclusion
This article explained the properties of the Rayleigh quotient.
Furthermore, it demonstrated the proof of the maximum and minimum values of the Rayleigh quotient using Lagrange multipliers.
Lastly, it provided a simple implementation example in Python.