Mixing
Solve $X^TX=A$ for $X$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
How does one solve the equation
$$X^TX=A$$
for $X$ given $A$ is an $n×n$ matrix, $X$ is $m×n$, and $rank(A)<min(m,n)$?
I know this must be simple, but I have been wrestling with it for some time now.
Thanks in advance for any help.
Edit: forgot to specify that A is symmetrical
linear-algebra matrices
asked Jul 21 at 7:07
Michael New
154
add a comment |Â
up vote
1
down vote
favorite
How does one solve the equation
$$X^TX=A$$
for $X$ given $A$ is an $n×n$ matrix, $X$ is $m×n$, and $rank(A)<min(m,n)$?
I know this must be simple, but I have been wrestling with it for some time now.
Thanks in advance for any help.
Edit: forgot to specify that A is symmetrical
linear-algebra matrices
asked Jul 21 at 7:07
Michael New
154
2
Maybe X is nxm? (or A is nxn?)
– gimusi
Jul 21 at 7:46
Yes, fixed. Thank you for the correction.
– Michael New
Jul 21 at 8:25
Have you tried to solve it for $n=1$ or $n=2$? What did you get?
– Somos
Jul 21 at 19:38
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
How does one solve the equation
$$X^TX=A$$
for $X$ given $A$ is an $n×n$ matrix, $X$ is $m×n$, and $rank(A)<min(m,n)$?
I know this must be simple, but I have been wrestling with it for some time now.
Thanks in advance for any help.
Edit: forgot to specify that A is symmetrical
linear-algebra matrices
asked Jul 21 at 7:07
Michael New
154
How does one solve the equation
$$X^TX=A$$
for $X$ given $A$ is an $n×n$ matrix, $X$ is $m×n$, and $rank(A)<min(m,n)$?
I know this must be simple, but I have been wrestling with it for some time now.
Thanks in advance for any help.
Edit: forgot to specify that A is symmetrical
linear-algebra matrices
asked Jul 21 at 7:07
Michael New
154
edited Jul 21 at 8:20
asked Jul 21 at 7:07
Michael New
154
asked Jul 21 at 7:07
Michael New
154
asked Jul 21 at 7:07
Michael New
154
154
2
Maybe X is nxm? (or A is nxn?)
– gimusi
Jul 21 at 7:46
Yes, fixed. Thank you for the correction.
– Michael New
Jul 21 at 8:25
Have you tried to solve it for $n=1$ or $n=2$? What did you get?
– Somos
Jul 21 at 19:38
add a comment |Â
2
Maybe X is nxm? (or A is nxn?)
– gimusi
Jul 21 at 7:46
Yes, fixed. Thank you for the correction.
– Michael New
Jul 21 at 8:25
Have you tried to solve it for $n=1$ or $n=2$? What did you get?
– Somos
Jul 21 at 19:38
2
2
Maybe X is nxm? (or A is nxn?)
– gimusi
Jul 21 at 7:46
Maybe X is nxm? (or A is nxn?)
– gimusi
Jul 21 at 7:46
Yes, fixed. Thank you for the correction.
– Michael New
Jul 21 at 8:25
Yes, fixed. Thank you for the correction.
– Michael New
Jul 21 at 8:25
Have you tried to solve it for $n=1$ or $n=2$? What did you get?
– Somos
Jul 21 at 19:38
Have you tried to solve it for $n=1$ or $n=2$? What did you get?
– Somos
Jul 21 at 19:38
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
accepted
Since $A$ is symmetric $n times n$, we can write it as $A=Q Lambda Q^T$, where Q is an orthogonal matrix whose columns are the eigenvectors of A, and Λ is a diagonal matrix whose entries are the eigenvalues of $A$.
We want to decompose $A=X^TX$, where $X$ is $m times n$.
Let $mathbfrank(A)=r<min(m, n)$, therefore, $A$ is not full rank and have $n-r$ eigenvalues equal to 0.
We can form $tildeQ$, $n times r$, by deleting the columns of $Q$ corresponding to the eigenvectors associated to the eigenvalues equal to 0, and also form $tildeLambda$, $r times r$, which is a diagonal matrix whose entries are the non-zero eigenvalues of $A$. Thus, we have
$$A=tildeQ tildeLambda tildeQ^T = tildeQ sqrttildeLambda sqrttildeLambda tildeQ^T = (sqrttildeLambda tildeQ^T)^T sqrttildeLambda tildeQ^T = X^TX,$$
where $X = sqrttildeLambda tildeQ^T$, with dimensions $r times n$.
The only problem is that $mathbfrank(A)=r=min(m, n)$, for $m=r$. To solve this issue, when forming $tildeQ$, delete all but one of the columns of $Q$ corresponding eigenvectors associated to the eigenvalues equal to 0. Doing this, $X$ will end up with dimensions $(r+1) times n$, satisfying the inequality $mathbfrank(A)=r<min(m, n)$, for $m=r+1$.
answered Jul 22 at 1:48
pedroszattoni
14819
Great explanation, thank you.
– Michael New
Jul 23 at 19:35
add a comment |Â
up vote
3
down vote
The solution can only exist for symmetric $A$. We can then write $A=O^T DO$ with $D$ diagonal (and with non-negative eigenvalues) and $O$ orthogonal. We can then define a square root of $D$ in the obvious way, obtaining $X=sqrtDO$ as one solution. For orthogonal $O'$, a more general solution is $X=O'sqrtDO$.
answered Jul 21 at 8:46
J.G.
13.2k11424
Thanks for the answer. I am interested in cases where A is not square and potentially not full rank, meaning that svd must be used in lieu of eigendecomposition. In this case, we cannot write A as $O^TDO$.
– Michael New
Jul 21 at 9:02
@MichaelNew But $X^T X=A$ implies $A^T =A$. You're allowed $0$ as an eigenvalue, though.
– J.G.
Jul 21 at 9:16
2
Symmetric is not enough. Solvable iff $A$ is positive semidefinte.
– A.Γ.
Jul 21 at 11:25
add a comment |Â
up vote
1
down vote
Assume $m=n$. The rows of $X$ are some $n$ vectors in $mathbbR^n$, say, $v_1,dots, v_n$. The $(i,j)$ element of $X^tX$ is the inner product $v_icdot v_j$. So there are at most $nchoose 2+n$ different entries in $X^tX$, but $n^2$ possible entries in a general $ntimes n$ matrix $A$. As a result, one cannot expect to solve the equation $X^tX=A$ for every $A$.
answered Jul 21 at 7:59
uniquesolution
7,700721
You are missing the fact that the rank of A is less than the (maximum possible) rank of X. I also forgot to specify that A is symmetrical, apologies for that (now included in the question). There is guaranteed to be a solution, I am just having trouble solving for it.
– Michael New
Jul 21 at 8:24
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Since $A$ is symmetric $n times n$, we can write it as $A=Q Lambda Q^T$, where Q is an orthogonal matrix whose columns are the eigenvectors of A, and Λ is a diagonal matrix whose entries are the eigenvalues of $A$.
We want to decompose $A=X^TX$, where $X$ is $m times n$.
Let $mathbfrank(A)=r<min(m, n)$, therefore, $A$ is not full rank and have $n-r$ eigenvalues equal to 0.
We can form $tildeQ$, $n times r$, by deleting the columns of $Q$ corresponding to the eigenvectors associated to the eigenvalues equal to 0, and also form $tildeLambda$, $r times r$, which is a diagonal matrix whose entries are the non-zero eigenvalues of $A$. Thus, we have
$$A=tildeQ tildeLambda tildeQ^T = tildeQ sqrttildeLambda sqrttildeLambda tildeQ^T = (sqrttildeLambda tildeQ^T)^T sqrttildeLambda tildeQ^T = X^TX,$$
where $X = sqrttildeLambda tildeQ^T$, with dimensions $r times n$.
The only problem is that $mathbfrank(A)=r=min(m, n)$, for $m=r$. To solve this issue, when forming $tildeQ$, delete all but one of the columns of $Q$ corresponding eigenvectors associated to the eigenvalues equal to 0. Doing this, $X$ will end up with dimensions $(r+1) times n$, satisfying the inequality $mathbfrank(A)=r<min(m, n)$, for $m=r+1$.
answered Jul 22 at 1:48
pedroszattoni
14819
Great explanation, thank you.
– Michael New
Jul 23 at 19:35
add a comment |Â
up vote
2
down vote
accepted
Since $A$ is symmetric $n times n$, we can write it as $A=Q Lambda Q^T$, where Q is an orthogonal matrix whose columns are the eigenvectors of A, and Λ is a diagonal matrix whose entries are the eigenvalues of $A$.
We want to decompose $A=X^TX$, where $X$ is $m times n$.
Let $mathbfrank(A)=r<min(m, n)$, therefore, $A$ is not full rank and have $n-r$ eigenvalues equal to 0.
We can form $tildeQ$, $n times r$, by deleting the columns of $Q$ corresponding to the eigenvectors associated to the eigenvalues equal to 0, and also form $tildeLambda$, $r times r$, which is a diagonal matrix whose entries are the non-zero eigenvalues of $A$. Thus, we have
$$A=tildeQ tildeLambda tildeQ^T = tildeQ sqrttildeLambda sqrttildeLambda tildeQ^T = (sqrttildeLambda tildeQ^T)^T sqrttildeLambda tildeQ^T = X^TX,$$
where $X = sqrttildeLambda tildeQ^T$, with dimensions $r times n$.
The only problem is that $mathbfrank(A)=r=min(m, n)$, for $m=r$. To solve this issue, when forming $tildeQ$, delete all but one of the columns of $Q$ corresponding eigenvectors associated to the eigenvalues equal to 0. Doing this, $X$ will end up with dimensions $(r+1) times n$, satisfying the inequality $mathbfrank(A)=r<min(m, n)$, for $m=r+1$.
answered Jul 22 at 1:48
pedroszattoni
14819
Great explanation, thank you.
– Michael New
Jul 23 at 19:35
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Since $A$ is symmetric $n times n$, we can write it as $A=Q Lambda Q^T$, where Q is an orthogonal matrix whose columns are the eigenvectors of A, and Λ is a diagonal matrix whose entries are the eigenvalues of $A$.
We want to decompose $A=X^TX$, where $X$ is $m times n$.
Let $mathbfrank(A)=r<min(m, n)$, therefore, $A$ is not full rank and have $n-r$ eigenvalues equal to 0.
We can form $tildeQ$, $n times r$, by deleting the columns of $Q$ corresponding to the eigenvectors associated to the eigenvalues equal to 0, and also form $tildeLambda$, $r times r$, which is a diagonal matrix whose entries are the non-zero eigenvalues of $A$. Thus, we have
$$A=tildeQ tildeLambda tildeQ^T = tildeQ sqrttildeLambda sqrttildeLambda tildeQ^T = (sqrttildeLambda tildeQ^T)^T sqrttildeLambda tildeQ^T = X^TX,$$
where $X = sqrttildeLambda tildeQ^T$, with dimensions $r times n$.
The only problem is that $mathbfrank(A)=r=min(m, n)$, for $m=r$. To solve this issue, when forming $tildeQ$, delete all but one of the columns of $Q$ corresponding eigenvectors associated to the eigenvalues equal to 0. Doing this, $X$ will end up with dimensions $(r+1) times n$, satisfying the inequality $mathbfrank(A)=r<min(m, n)$, for $m=r+1$.
answered Jul 22 at 1:48
pedroszattoni
14819
Since $A$ is symmetric $n times n$, we can write it as $A=Q Lambda Q^T$, where Q is an orthogonal matrix whose columns are the eigenvectors of A, and Λ is a diagonal matrix whose entries are the eigenvalues of $A$.
We want to decompose $A=X^TX$, where $X$ is $m times n$.
Let $mathbfrank(A)=r<min(m, n)$, therefore, $A$ is not full rank and have $n-r$ eigenvalues equal to 0.
We can form $tildeQ$, $n times r$, by deleting the columns of $Q$ corresponding to the eigenvectors associated to the eigenvalues equal to 0, and also form $tildeLambda$, $r times r$, which is a diagonal matrix whose entries are the non-zero eigenvalues of $A$. Thus, we have
$$A=tildeQ tildeLambda tildeQ^T = tildeQ sqrttildeLambda sqrttildeLambda tildeQ^T = (sqrttildeLambda tildeQ^T)^T sqrttildeLambda tildeQ^T = X^TX,$$
where $X = sqrttildeLambda tildeQ^T$, with dimensions $r times n$.
The only problem is that $mathbfrank(A)=r=min(m, n)$, for $m=r$. To solve this issue, when forming $tildeQ$, delete all but one of the columns of $Q$ corresponding eigenvectors associated to the eigenvalues equal to 0. Doing this, $X$ will end up with dimensions $(r+1) times n$, satisfying the inequality $mathbfrank(A)=r<min(m, n)$, for $m=r+1$.
answered Jul 22 at 1:48
pedroszattoni
14819
answered Jul 22 at 1:48
pedroszattoni
14819
answered Jul 22 at 1:48
pedroszattoni
14819
answered Jul 22 at 1:48
pedroszattoni
14819
14819
Great explanation, thank you.
– Michael New
Jul 23 at 19:35
add a comment |Â
Great explanation, thank you.
– Michael New
Jul 23 at 19:35
Great explanation, thank you.
– Michael New
Jul 23 at 19:35
Great explanation, thank you.
– Michael New
Jul 23 at 19:35
add a comment |Â
up vote
3
down vote
The solution can only exist for symmetric $A$. We can then write $A=O^T DO$ with $D$ diagonal (and with non-negative eigenvalues) and $O$ orthogonal. We can then define a square root of $D$ in the obvious way, obtaining $X=sqrtDO$ as one solution. For orthogonal $O'$, a more general solution is $X=O'sqrtDO$.
answered Jul 21 at 8:46
J.G.
13.2k11424
Thanks for the answer. I am interested in cases where A is not square and potentially not full rank, meaning that svd must be used in lieu of eigendecomposition. In this case, we cannot write A as $O^TDO$.
– Michael New
Jul 21 at 9:02
@MichaelNew But $X^T X=A$ implies $A^T =A$. You're allowed $0$ as an eigenvalue, though.
– J.G.
Jul 21 at 9:16
2
Symmetric is not enough. Solvable iff $A$ is positive semidefinte.
– A.Γ.
Jul 21 at 11:25
add a comment |Â
up vote
3
down vote
The solution can only exist for symmetric $A$. We can then write $A=O^T DO$ with $D$ diagonal (and with non-negative eigenvalues) and $O$ orthogonal. We can then define a square root of $D$ in the obvious way, obtaining $X=sqrtDO$ as one solution. For orthogonal $O'$, a more general solution is $X=O'sqrtDO$.
answered Jul 21 at 8:46
J.G.
13.2k11424
Thanks for the answer. I am interested in cases where A is not square and potentially not full rank, meaning that svd must be used in lieu of eigendecomposition. In this case, we cannot write A as $O^TDO$.
– Michael New
Jul 21 at 9:02
@MichaelNew But $X^T X=A$ implies $A^T =A$. You're allowed $0$ as an eigenvalue, though.
– J.G.
Jul 21 at 9:16
2
Symmetric is not enough. Solvable iff $A$ is positive semidefinte.
– A.Γ.
Jul 21 at 11:25
add a comment |Â
up vote
3
down vote
up vote
3
down vote
The solution can only exist for symmetric $A$. We can then write $A=O^T DO$ with $D$ diagonal (and with non-negative eigenvalues) and $O$ orthogonal. We can then define a square root of $D$ in the obvious way, obtaining $X=sqrtDO$ as one solution. For orthogonal $O'$, a more general solution is $X=O'sqrtDO$.
answered Jul 21 at 8:46
J.G.
13.2k11424
The solution can only exist for symmetric $A$. We can then write $A=O^T DO$ with $D$ diagonal (and with non-negative eigenvalues) and $O$ orthogonal. We can then define a square root of $D$ in the obvious way, obtaining $X=sqrtDO$ as one solution. For orthogonal $O'$, a more general solution is $X=O'sqrtDO$.
answered Jul 21 at 8:46
J.G.
13.2k11424
answered Jul 21 at 8:46
J.G.
13.2k11424
answered Jul 21 at 8:46
J.G.
13.2k11424
answered Jul 21 at 8:46
J.G.
13.2k11424
13.2k11424
Thanks for the answer. I am interested in cases where A is not square and potentially not full rank, meaning that svd must be used in lieu of eigendecomposition. In this case, we cannot write A as $O^TDO$.
– Michael New
Jul 21 at 9:02
@MichaelNew But $X^T X=A$ implies $A^T =A$. You're allowed $0$ as an eigenvalue, though.
– J.G.
Jul 21 at 9:16
2
Symmetric is not enough. Solvable iff $A$ is positive semidefinte.
– A.Γ.
Jul 21 at 11:25
add a comment |Â
Thanks for the answer. I am interested in cases where A is not square and potentially not full rank, meaning that svd must be used in lieu of eigendecomposition. In this case, we cannot write A as $O^TDO$.
– Michael New
Jul 21 at 9:02
@MichaelNew But $X^T X=A$ implies $A^T =A$. You're allowed $0$ as an eigenvalue, though.
– J.G.
Jul 21 at 9:16
2
Symmetric is not enough. Solvable iff $A$ is positive semidefinte.
– A.Γ.
Jul 21 at 11:25
Thanks for the answer. I am interested in cases where A is not square and potentially not full rank, meaning that svd must be used in lieu of eigendecomposition. In this case, we cannot write A as $O^TDO$.
– Michael New
Jul 21 at 9:02
Thanks for the answer. I am interested in cases where A is not square and potentially not full rank, meaning that svd must be used in lieu of eigendecomposition. In this case, we cannot write A as $O^TDO$.
– Michael New
Jul 21 at 9:02
@MichaelNew But $X^T X=A$ implies $A^T =A$. You're allowed $0$ as an eigenvalue, though.
– J.G.
Jul 21 at 9:16
@MichaelNew But $X^T X=A$ implies $A^T =A$. You're allowed $0$ as an eigenvalue, though.
– J.G.
Jul 21 at 9:16
2
2
Symmetric is not enough. Solvable iff $A$ is positive semidefinte.
– A.Γ.
Jul 21 at 11:25
Symmetric is not enough. Solvable iff $A$ is positive semidefinte.
– A.Γ.
Jul 21 at 11:25
add a comment |Â
up vote
1
down vote
Assume $m=n$. The rows of $X$ are some $n$ vectors in $mathbbR^n$, say, $v_1,dots, v_n$. The $(i,j)$ element of $X^tX$ is the inner product $v_icdot v_j$. So there are at most $nchoose 2+n$ different entries in $X^tX$, but $n^2$ possible entries in a general $ntimes n$ matrix $A$. As a result, one cannot expect to solve the equation $X^tX=A$ for every $A$.
answered Jul 21 at 7:59
uniquesolution
7,700721
You are missing the fact that the rank of A is less than the (maximum possible) rank of X. I also forgot to specify that A is symmetrical, apologies for that (now included in the question). There is guaranteed to be a solution, I am just having trouble solving for it.
– Michael New
Jul 21 at 8:24
add a comment |Â
up vote
1
down vote
Assume $m=n$. The rows of $X$ are some $n$ vectors in $mathbbR^n$, say, $v_1,dots, v_n$. The $(i,j)$ element of $X^tX$ is the inner product $v_icdot v_j$. So there are at most $nchoose 2+n$ different entries in $X^tX$, but $n^2$ possible entries in a general $ntimes n$ matrix $A$. As a result, one cannot expect to solve the equation $X^tX=A$ for every $A$.
answered Jul 21 at 7:59
uniquesolution
7,700721
You are missing the fact that the rank of A is less than the (maximum possible) rank of X. I also forgot to specify that A is symmetrical, apologies for that (now included in the question). There is guaranteed to be a solution, I am just having trouble solving for it.
– Michael New
Jul 21 at 8:24
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Assume $m=n$. The rows of $X$ are some $n$ vectors in $mathbbR^n$, say, $v_1,dots, v_n$. The $(i,j)$ element of $X^tX$ is the inner product $v_icdot v_j$. So there are at most $nchoose 2+n$ different entries in $X^tX$, but $n^2$ possible entries in a general $ntimes n$ matrix $A$. As a result, one cannot expect to solve the equation $X^tX=A$ for every $A$.
answered Jul 21 at 7:59
uniquesolution
7,700721
Assume $m=n$. The rows of $X$ are some $n$ vectors in $mathbbR^n$, say, $v_1,dots, v_n$. The $(i,j)$ element of $X^tX$ is the inner product $v_icdot v_j$. So there are at most $nchoose 2+n$ different entries in $X^tX$, but $n^2$ possible entries in a general $ntimes n$ matrix $A$. As a result, one cannot expect to solve the equation $X^tX=A$ for every $A$.
answered Jul 21 at 7:59
uniquesolution
7,700721
answered Jul 21 at 7:59
uniquesolution
7,700721
answered Jul 21 at 7:59
uniquesolution
7,700721
answered Jul 21 at 7:59
uniquesolution
7,700721
7,700721
You are missing the fact that the rank of A is less than the (maximum possible) rank of X. I also forgot to specify that A is symmetrical, apologies for that (now included in the question). There is guaranteed to be a solution, I am just having trouble solving for it.
– Michael New
Jul 21 at 8:24
add a comment |Â
You are missing the fact that the rank of A is less than the (maximum possible) rank of X. I also forgot to specify that A is symmetrical, apologies for that (now included in the question). There is guaranteed to be a solution, I am just having trouble solving for it.
– Michael New
Jul 21 at 8:24
You are missing the fact that the rank of A is less than the (maximum possible) rank of X. I also forgot to specify that A is symmetrical, apologies for that (now included in the question). There is guaranteed to be a solution, I am just having trouble solving for it.
– Michael New
Jul 21 at 8:24
You are missing the fact that the rank of A is less than the (maximum possible) rank of X. I also forgot to specify that A is symmetrical, apologies for that (now included in the question). There is guaranteed to be a solution, I am just having trouble solving for it.
– Michael New
Jul 21 at 8:24
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858299%2fsolve-xtx-a-for-x%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
Maybe X is nxm? (or A is nxn?)
– gimusi
Jul 21 at 7:46
Yes, fixed. Thank you for the correction.
– Michael New
Jul 21 at 8:25
Have you tried to solve it for $n=1$ or $n=2$? What did you get?
– Somos
Jul 21 at 19:38