为 R 中的任何 m * n 矩阵 A 求解齐次系统 Ax = 0(找到 A 的零空间基) [英] Solve homogenous system Ax = 0 for any m * n matrix A in R (find null space basis for A)
问题描述
如何求解一个齐次系统 Ax = 0，当 A 是任何 m * n 矩阵(不一定是平方)时R?
How to solve a homogenous system Ax = 0, when A is any m * n matrix (not necessarily a square one) in R?
# A=[-0.1 0.1]= 1x2 matrix; x=2x1 to be found; 0: 1x1 zero matrix
A <- t(matrix(c(-0.1,0.1)))
这个问题似乎相当于找到一个Rn的核(零空间)->Rm(不能做上标；抱歉)线性变换.
This question seems to be equivalent of finding the kernel (null space) of an Rn -> Rm (can't do superscript; sorry) linear transformation.
推荐答案
无论如何，上面特定矩阵
A的解决方案对我来说就足够了.
Anyway, the solution for the above specific matrix
Awill suffice to me.
我们可以目测它，x = (a, a)，其中a是一个任意值.
We can eye-spot it, x = (a, a), where a is an arbitrary value.
下面的函数NullSpace使用上述理论找到A的零空间.在情况 1 中，零空间几乎为零；而在情况 2 到 4 中，返回一个矩阵，其列跨越零空间.
The following function NullSpace finds the null space of A using the above theory. In case 1, the null space is trivially zero; while in cases 2 to 4 a matrix is returned whose columns span the null space.
NullSpace <- function (A) {
m <- dim(A)[1]; n <- dim(A)[2]
## QR factorization and rank detection
QR <- base::qr.default(A)
r <- QR$rank
## cases 2 to 4
if ((r < min(m, n)) || (m < n)) {
R <- QR$qr[1:r, , drop = FALSE]
P <- QR$pivot
F <- R[, (r + 1):n, drop = FALSE]
I <- base::diag(1, n - r)
B <- -1.0 * base::backsolve(R, F, r)
Y <- base::rbind(B, I)
X <- Y[base::order(P), , drop = FALSE]
return(X)
}
## case 1
return(base::matrix(0, n, 1))
}
使用您的示例矩阵，它正确返回零空间.
With your example matrix, it correctly returns the null space.
A1 <- matrix(c(-0.1, 0.1), 1, 2)
NullSpace(A1)
# [,1]
#[1,] 1
#[2,] 1
我们也可以尝试一个随机的例子.
We can also try a random example.
set.seed(0)
A2 <- matrix(runif(10), 2, 5)
# [,1] [,2] [,3] [,4] [,5]
#[1,] 0.8966972 0.3721239 0.9082078 0.8983897 0.6607978
#[2,] 0.2655087 0.5728534 0.2016819 0.9446753 0.6291140
X <- NullSpace(A2)
# [,1] [,2] [,3]
#[1,] -1.0731435 -0.393154 -0.3481344
#[2,] 0.1453199 -1.466849 -0.9368564
#[3,] 1.0000000 0.000000 0.0000000
#[4,] 0.0000000 1.000000 0.0000000
#[5,] 0.0000000 0.000000 1.0000000
## X indeed solves A2 %*% X = 0
A2 %*% X
# [,1] [,2] [,3]
#[1,] 2.220446e-16 -1.110223e-16 -2.220446e-16
#[2,] 5.551115e-17 -1.110223e-16 -1.110223e-16
<小时>
求标准正交基
我的函数 NullSpace 返回零空间的非正交基.另一种方法是将 QR 分解应用于 t(A)(A 的转置)，获得排名 r，并保留最终的
Finding orthonormal basis
My function NullSpace returns an non-orthogonal basis for the null space. An alternative is to apply QR factorization to t(A) (transpose of A), get the rank r, and retain the final (n - r) columns of the Q matrix. This gives an orthonormal basis for the null space.
pracma 包中的 nullspace 函数是一个现有的实现.让我们以上面的矩阵 A2 为例进行演示.
The nullspace function from pracma package is an existing implementation. Let's take matrix A2 above for a demonstration.
library(pracma)
X2 <- nullspace(A2)
# [,1] [,2] [,3]
#[1,] -0.67453687 -0.24622524 -0.2182437
#[2,] 0.27206765 -0.69479881 -0.4260258
#[3,] 0.67857488 0.07429112 0.0200459
#[4,] -0.07098962 0.62990141 -0.2457700
#[5,] -0.07399872 -0.23309397 0.8426547
## it indeed solves A2 %*% X = 0
A2 %*% X2
# [,1] [,2] [,3]
#[1,] 2.567391e-16 1.942890e-16 0.000000e+00
#[2,] 6.938894e-17 -5.551115e-17 -1.110223e-16
## it has orthonormal columns
round(crossprod(X2), 15)
# [,1] [,2] [,3]
#[1,] 1 0 0
#[2,] 0 1 0
#[3,] 0 0 1
<小时>
附录:图片的 Markdown(需要 MathJax 支持)
Let $A$ be $m imes n$, then its null space is ${x: Ax = 0}$. To find a solution of $Ax = 0$, the conventional method is Gaussian elimination that reduces $A$ into a row echelon form. However, let's consider the QR factorization (with column pivoting) approach, where a sequence of Householder transforms are applied to both sides of $Ax = 0$, reducing the equation to $RP'x = 0$, where $P$ is an $n imes n$ column permutation matrix. What $R$ looks like depends on the relationship of $m$ and $n$, as well as the rank of $A$, denoted by $r$.
1. If $m ge n = r$, $R$ is an $n imes n$ full-rank upper triangular matrix, which looks like $$egin{pmatrix} imes & imes & imes & imes \ & imes & imes & imes \ & & imes & imes \ & & & imesend{pmatrix}$$
2. If $m ge n > r$, $R$ is an $n imes n$ rank-deficient upper triangular matrix, which looks like $$egin{pmatrix} imes & imes & imes & imes \ & imes & imes & imes \ & & imes & imes \ & & & 0end{pmatrix}$$
3. If $r = m < n$, $R$ is an $m imes n$ full-rank matrix which looks like $$egin{pmatrix} imes & imes & imes & imes & imes & imes & imes \ & imes & imes & imes & imes & imes & imes\ & & imes & imes & imes & imes & imes\ & & & imes & imes & imes & imesend{pmatrix}$$
4. If $r < m < n$, $R$ is an $m imes n$ rank-deficient matrix which looks like $$egin{pmatrix} imes & imes & imes & imes & imes & imes & imes \ & imes & imes & imes & imes & imes & imes\ & & imes & imes & imes & imes & imes\ & & & 0 & 0 & 0 & 0end{pmatrix}$$.
In all cases, the first $r$ non-zero rows of $R$ can be partiontioned into $egin{pmatrix} U & Fend{pmatrix}$, where $U$ is an $r imes r$ full-rank upper triangular matrix and $F$ is an $r imes (n - r)$ rectangular matrix. The null space of $A$ has dimension $(n - r)$ and can be characterized by an $ n imes (n - r)$ matrix $X$, such that $RP'X = 0$. In practice, $X$ is obtained in two steps.
1. Let $Y$ be an $ n imes (n - r)$ matrix and solve $RY = 0$. Clearly $Y$ can not be uniquely determined as the linear system has $(n - r)$ free parameters. A common solution is to find $Y = left(egin{smallmatrix} B \ I end{smallmatrix}
ight)$, where $I$ is an $(n - r) imes (n - r)$ identity matrix. Then $B$ can be uniquely solved from $UB = -F$ using back substitution.
2. Solve $P'X = Y$ for $X = PY$, which is simply a row permutation of $Y$.
这篇关于为 R 中的任何 m * n 矩阵 A 求解齐次系统 Ax = 0(找到 A 的零空间基)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
