Credit risk is based, in part, on credit migration matrices that are used to describe changes in credit worthiness, usually on an annual basis. However, the time horizons associated with different portfolios, and therefore the risk horizons, may not always coincide. To compare risk in a meaningful way, they should at least be equal. One way to render the risk horizons equivalent is to alter the credit migration matrix in a special way. This leads to the problem known as the nth root of a matrix which will be discussed in this article.
In risk management, credit migration matrices are used in Monte Carlo simulations to help compute risk profiles. They describe the behavior through time of a number of states each associated with a probability of occurrence, and are usually represented in the form of a matrix of probabilities called a state transition matrix (STM). Credit migration data is made available by rating agencies like Moody's Investor Services and Standard and Poor's. Bond rating is important because it is linked to the interest rate paid on debt. These matrices have some useful properties. If P(1) is a one year STM, then the so-called two-step STM, P(2) = P(1) x P(1) has a time horizon of two years. In general, P(n) has a time horizon of n consecutive years, but obtaining it in this way does not account for any autocorrelations over multiple time horizons. This is a limitation since a down grading in a credit rating often leads to further downgrading, whereas upgrades tend to lead to quiet periods.
A problem arises when risk must be aggregated across portfolios with different time horizons. Before this can occur, the risk must be represented so that it applies over the same time horizon. One way to do this is to alter the migration matrix in a special way. This leads to the problem of computing an nth root of the migration matrix which serves to contract the time horizon. Contracting the time horizon is far less straightforward than expanding it and can require special matrix factorization algorithms. Further, the matrix root is not necessarily unique, nor does it always exist. When the matrix P is positive definite symmetric, the nth root can be found using eigenvalue decomposition. Unfortunately, this is rarely so, and finding it requires more sophisticated means.
Nicholas Higham showed how to compute the square root of a matrix using Newton descent methods but their convergence properties are problematic. Ake Bjorck showed how the Schur decomposition led to an efficient way to compute the matrix square root. An interesting aspect of the square root of a matrix is that an m by m identity matrix has infinitely many square roots for m>2.
In contrast, the matrix
has no square root.
THE REAL NTH ROOT
Formulating the problem of computing the real nth root of a matrix is straightforward. Given a non-negative integer n, a real matrix P, find a real F such that Fn = P. However, computing the matrix root is no simple matter, and the theory that describes it is not easy. For instance, it is important to distinguish between roots that are functions of the matrix, and those that are not. If no such distinction is made, it is difficult to characterize the roots of a matrix in a meaningful way, and further, the development of root finding algorithms based on constructive means is circumspect.
This problem has been solved with the development of an algorithm that can be used to compute the real nth root of a real non-symmetric matrix based on the Schur decomposition. This article will discuss aspects such as its existence, asymptotic behavior and computational complexity foregoing lengthy mathematical derivation.
If a matrix B has at least one negative eigenvalue, no real even root exists that is a function of B. When n is odd, a negative real eigenvalue does not preclude the existence of the nth root. The number of square roots is 2r+c where r is the number of positive real-value eigenvalues and c is the number of distinct complex conjugate eigenvalue pairs.
Further insight into the existence can be gained by looking at the eigenvalues of an arbitrary STM. Geshgorin's Theorem gives bounds on the radii of the disks D in which the eigenvalues lie. It is assumed that the eigenvalues * of P lie in the disks
So when a diagonal element of P, Pii, is small, Di extends into the left-half complex plane. In fact, when Pii = 0, half of Di is in this region. As Pii is increased, the likelihood of a negative real eigenvalue is decreased. When Pii >= 0.5, P has no negative real eigenvalues. This effect can be illustrated with simple simulation in which the probability of a negative eigenvalue was computed based on 10,000 randomly generated 10 by 10 STM. The results are plotted in figure 1. As expected, the number of negative eigenvalues is zero when Pii = 0.5. In a similar simulation, 10,000, randomly generated 10 by 10 STM were filled with IID uniform deviates. Only 5.549% did not harbor a negative eigenvalue. This implies that an even root of an arbitrary STM does not always exist.
EXAMPLE: NON-UNIQUENESS
In this example two real square roots of an annualized credit migration matrix will be computed. The solution is not unique. Given
two legitimate six-month migration matrices are
Both Pa(1/2) and Pb(1/2) are STM because their entries are probabilities which have a row wise sum of unity.
CONCLUSION
This article discussed the problem of computing the real nth root of a real matrix based on the Schur decomposition. The real root of a matrix does not always exist nor is it necessarily unique. The presence of a negative eigenvalue implies that an even real root cannot be computed. A simple simulation revealed that negative eigenvalues were present in well over 90% of the 10,000 randomly generated credit migration matrices.
When a matrix has no negative or zero eigenvalues that limn*(infinity)P1/n = I, where I is the identity matrix. This is an intuitively satisfying result. As n*(infinity), the time horizon decreases to 0, and there is a lesser chance that the next state will differ from the current state because the process has less time to move away from its current state. It can be shown that the rate of convergence of P(1/n) to 1 occurs at rate 1/n.
The number of operations required to compute the real nth root of a real matrix P**10x10 can be bounded above by (n-1)3 x m(m-1)/2+m. Usually a far lesser number of operations is required. So, for example, the 497th root of a P**10x10 requires no more than 98,839,388,170 operations. Alternative methods for computing the nth root of a matrix also exists. Constrained optimization is one such method.
This week's Learning Curve was written by G. Finn Wredenhagen, a director of research with Anabasis Corp., in Toronto, Canada.
