2
$\begingroup$

Assume I have a system of linear equations $Au = b$ where A is some $M\times N$ matrix, u is $N\times 1$ unknown variables vector, and b is $M\times 1$. Now, further assume that I know that some elements of $u$ are linearly dependent on the other elements of $u$. I.e., we can write $u$ as $u=[u_1, u_2]$ where $u_1$ is $N_1\times 1$, and $u_2$ is $N_2 \times 1$ and $N_1+N_2=N$ and it is known that $u_1 = Cu_2$, where $C$ is some unknown matrix. Is there any way that this knowledge (that we know that some elements of u are dependent and we know which elements, but we don't know the dependency matrix C) can help me improve the complexity of solving the system of equations $Au=b$? I.e., is there any way it can simplify the complexity of the gaussian elimination (or any other algorithm for solving a system of linear equations)?

Thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ If $Au=b$, $A$ is $M\times N$, and $u$ is $N\times1$, then $b$ had better be $M\times1$, not $N\times1$. $\endgroup$
    – Gerry Myerson
    Commented Jun 22, 2020 at 7:15
  • $\begingroup$ correct - I've updated the question $\endgroup$
    – MRm
    Commented Jun 22, 2020 at 7:41
  • $\begingroup$ What do you mean by "solving" a system of linear equations when $M\neq N$? There may be zero solutions, or infinite solutions. $\endgroup$
    – Federico Poloni
    Commented Jun 22, 2020 at 7:46

1 Answer 1

Reset to default
2
$\begingroup$

I don't think so. Given any two vectors $u_1$ and $u_2 \neq 0$, there is always a matrix $C$ such that $u_1 = Cu_2$. So you have no additional information, essentially.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Yes, yes, yes! The OP is saying that some of the coordinates are linearly dependent (in that one is a multiple of the other). But that’s true for literally any two real numbers. So the OP is saying literally nothing. $\endgroup$
    – Pat Devlin
    Commented Jun 22, 2020 at 13:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .