Overdetermined linear system?
$begingroup$
What should be the conditions on coefficients $a_i$ and $b_i$ such that the following overdetermined linear system of equations has unique solution.
$$a_i x+y=b_i$$
where $i=1,2,3...,n$.
The system represents $n$ straight lines and it is possible to make them ins
tersect at one point, hence sytem must have a unique solution for some $a_i,b_i$.
linear-algebra systems-of-equations
asked Dec 17 '18 at 6:30
ershersh
408113
$endgroup$
add a comment |
$begingroup$
What should be the conditions on coefficients $a_i$ and $b_i$ such that the following overdetermined linear system of equations has unique solution.
$$a_i x+y=b_i$$
where $i=1,2,3...,n$.
The system represents $n$ straight lines and it is possible to make them ins
tersect at one point, hence sytem must have a unique solution for some $a_i,b_i$.
linear-algebra systems-of-equations
asked Dec 17 '18 at 6:30
ershersh
408113
$endgroup$
$begingroup$
Where is $b_i$ in your equation?
$endgroup$
– induction601
Dec 17 '18 at 6:35
$begingroup$
Typo! Fixed. Sorry
$endgroup$
– ersh
Dec 17 '18 at 6:42
add a comment |
$begingroup$
What should be the conditions on coefficients $a_i$ and $b_i$ such that the following overdetermined linear system of equations has unique solution.
$$a_i x+y=b_i$$
where $i=1,2,3...,n$.
The system represents $n$ straight lines and it is possible to make them ins
tersect at one point, hence sytem must have a unique solution for some $a_i,b_i$.
linear-algebra systems-of-equations
asked Dec 17 '18 at 6:30
ershersh
408113
$endgroup$
What should be the conditions on coefficients $a_i$ and $b_i$ such that the following overdetermined linear system of equations has unique solution.
$$a_i x+y=b_i$$
where $i=1,2,3...,n$.
The system represents $n$ straight lines and it is possible to make them ins
tersect at one point, hence sytem must have a unique solution for some $a_i,b_i$.
linear-algebra systems-of-equations
linear-algebra systems-of-equations
asked Dec 17 '18 at 6:30
ershersh
408113
asked Dec 17 '18 at 6:30
ershersh
408113
edited Dec 17 '18 at 6:41
ersh
asked Dec 17 '18 at 6:30
ershersh
408113
asked Dec 17 '18 at 6:30
ershersh
408113
asked Dec 17 '18 at 6:30
ershersh
408113
408113
$begingroup$
Where is $b_i$ in your equation?
$endgroup$
– induction601
Dec 17 '18 at 6:35
$begingroup$
Typo! Fixed. Sorry
$endgroup$
– ersh
Dec 17 '18 at 6:42
add a comment |
$begingroup$
Where is $b_i$ in your equation?
$endgroup$
– induction601
Dec 17 '18 at 6:35
$begingroup$
Typo! Fixed. Sorry
$endgroup$
– ersh
Dec 17 '18 at 6:42
$begingroup$
Where is $b_i$ in your equation?
$endgroup$
– induction601
Dec 17 '18 at 6:35
$begingroup$
Where is $b_i$ in your equation?
$endgroup$
– induction601
Dec 17 '18 at 6:35
$begingroup$
Typo! Fixed. Sorry
$endgroup$
– ersh
Dec 17 '18 at 6:42
$begingroup$
Typo! Fixed. Sorry
$endgroup$
– ersh
Dec 17 '18 at 6:42
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The system is over-determined for $n>2$ but here is a general method. We can write the augmented matrix for the system $Abegin{bmatrix}x\yend{bmatrix}=B$ as under:
$begin{bmatrix}a_1&1&Big|&b_1\a_2&1&Big|&b_2\vdots&vdots&Big|&vdots\a_n&1&Big|&b_nend{bmatrix}$
For a unique solution to exist, we should have $2$ linearly-independent equations to solve for the $2$ unknowns. In other words, the rank of the coefficient and augmented matrices should be $2$. Recall that no more than $2$ vectors in $Bbb R^2$ can be linearly independent, so the rank of the coefficient matrix $A, text{rank}(A)le2$. For $text{rank}(A)=2$, we need to ensure at-least two $a_i$ are distinct. Say we have distinct $a_1ne0,a_2ne a_1$.
The point of intersection of $a_1x+y=b_1,a_2x+y=b_2$ is given by $(X,Y)=displaystyleBig(frac{b_1-b_2}{a_1-a_2},frac{a_1b_2-a_2b_1}{a_1-a_2}Big)$.
$displaystyle R_ito R_i-frac{a_i}{a_1}cdot R_1, i>1$
$displaystyle R_jto R_j-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdot R_2, j>2$
$simbegin{bmatrix}a_1&1&Big|&b_1\0&1-frac{a_2}{a_1}&Big|&b_2-frac{a_2}{a_1}cdot b_1\0&0&Big|&b'_3\vdots&vdots&Big|&vdots\0&0&Big|&b'_nend{bmatrix}$
$displaystyle b'_i=b_i-frac{a_i}{a_1}cdot b_1-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdotBig[b_2-frac{a_2}{a_1}cdot b_1Big] forall i>2$
For the rank of the augmented matrix to be $0$, we require $b'_i=0$
$displaystyletherefore b_i=frac{(a_i-a_2)b_1+(a_1-a_i)b_2}{a_1-a_2}=Big[frac{b_1-b_2}{a_1-a_2}Big]cdot a_i+Big(frac{a_1b_2-a_2b_1}{a_1-a_2}Big), forall i>2$
Therefore, if:
There are two lines $L_i,L_j$ not parallel to each other $(a_ine a_j)$ intersecting at $(X,Y)$;
$displaystyle b_k=Big[frac{b_i-b_j}{a_i-a_j}Big]cdot a_k+Big(frac{a_ib_j-a_jb_i}{a_i-a_j}Big)=Xa_k+Y, forall kne i,j$; that is, $(X,Y)$ lies on all the remaining lines;
Then, the straight lines $L_i:= a_ix+y=b_i,iin{1,2,...,n}$ intersect at the point $displaystyle(X,Y)=Big(frac{b_i-b_j}{a_i-a_j},frac{a_ib_j-a_jb_i}{a_i-a_j}Big)$ uniquely.
answered Dec 17 '18 at 8:07
Shubham JohriShubham Johri
5,192717
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3043601%2foverdetermined-linear-system%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The system is over-determined for $n>2$ but here is a general method. We can write the augmented matrix for the system $Abegin{bmatrix}x\yend{bmatrix}=B$ as under:
$begin{bmatrix}a_1&1&Big|&b_1\a_2&1&Big|&b_2\vdots&vdots&Big|&vdots\a_n&1&Big|&b_nend{bmatrix}$
For a unique solution to exist, we should have $2$ linearly-independent equations to solve for the $2$ unknowns. In other words, the rank of the coefficient and augmented matrices should be $2$. Recall that no more than $2$ vectors in $Bbb R^2$ can be linearly independent, so the rank of the coefficient matrix $A, text{rank}(A)le2$. For $text{rank}(A)=2$, we need to ensure at-least two $a_i$ are distinct. Say we have distinct $a_1ne0,a_2ne a_1$.
The point of intersection of $a_1x+y=b_1,a_2x+y=b_2$ is given by $(X,Y)=displaystyleBig(frac{b_1-b_2}{a_1-a_2},frac{a_1b_2-a_2b_1}{a_1-a_2}Big)$.
$displaystyle R_ito R_i-frac{a_i}{a_1}cdot R_1, i>1$
$displaystyle R_jto R_j-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdot R_2, j>2$
$simbegin{bmatrix}a_1&1&Big|&b_1\0&1-frac{a_2}{a_1}&Big|&b_2-frac{a_2}{a_1}cdot b_1\0&0&Big|&b'_3\vdots&vdots&Big|&vdots\0&0&Big|&b'_nend{bmatrix}$
$displaystyle b'_i=b_i-frac{a_i}{a_1}cdot b_1-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdotBig[b_2-frac{a_2}{a_1}cdot b_1Big] forall i>2$
For the rank of the augmented matrix to be $0$, we require $b'_i=0$
$displaystyletherefore b_i=frac{(a_i-a_2)b_1+(a_1-a_i)b_2}{a_1-a_2}=Big[frac{b_1-b_2}{a_1-a_2}Big]cdot a_i+Big(frac{a_1b_2-a_2b_1}{a_1-a_2}Big), forall i>2$
Therefore, if:
There are two lines $L_i,L_j$ not parallel to each other $(a_ine a_j)$ intersecting at $(X,Y)$;
$displaystyle b_k=Big[frac{b_i-b_j}{a_i-a_j}Big]cdot a_k+Big(frac{a_ib_j-a_jb_i}{a_i-a_j}Big)=Xa_k+Y, forall kne i,j$; that is, $(X,Y)$ lies on all the remaining lines;
Then, the straight lines $L_i:= a_ix+y=b_i,iin{1,2,...,n}$ intersect at the point $displaystyle(X,Y)=Big(frac{b_i-b_j}{a_i-a_j},frac{a_ib_j-a_jb_i}{a_i-a_j}Big)$ uniquely.
answered Dec 17 '18 at 8:07
Shubham JohriShubham Johri
5,192717
$endgroup$
add a comment |
$begingroup$
The system is over-determined for $n>2$ but here is a general method. We can write the augmented matrix for the system $Abegin{bmatrix}x\yend{bmatrix}=B$ as under:
$begin{bmatrix}a_1&1&Big|&b_1\a_2&1&Big|&b_2\vdots&vdots&Big|&vdots\a_n&1&Big|&b_nend{bmatrix}$
For a unique solution to exist, we should have $2$ linearly-independent equations to solve for the $2$ unknowns. In other words, the rank of the coefficient and augmented matrices should be $2$. Recall that no more than $2$ vectors in $Bbb R^2$ can be linearly independent, so the rank of the coefficient matrix $A, text{rank}(A)le2$. For $text{rank}(A)=2$, we need to ensure at-least two $a_i$ are distinct. Say we have distinct $a_1ne0,a_2ne a_1$.
The point of intersection of $a_1x+y=b_1,a_2x+y=b_2$ is given by $(X,Y)=displaystyleBig(frac{b_1-b_2}{a_1-a_2},frac{a_1b_2-a_2b_1}{a_1-a_2}Big)$.
$displaystyle R_ito R_i-frac{a_i}{a_1}cdot R_1, i>1$
$displaystyle R_jto R_j-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdot R_2, j>2$
$simbegin{bmatrix}a_1&1&Big|&b_1\0&1-frac{a_2}{a_1}&Big|&b_2-frac{a_2}{a_1}cdot b_1\0&0&Big|&b'_3\vdots&vdots&Big|&vdots\0&0&Big|&b'_nend{bmatrix}$
$displaystyle b'_i=b_i-frac{a_i}{a_1}cdot b_1-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdotBig[b_2-frac{a_2}{a_1}cdot b_1Big] forall i>2$
For the rank of the augmented matrix to be $0$, we require $b'_i=0$
$displaystyletherefore b_i=frac{(a_i-a_2)b_1+(a_1-a_i)b_2}{a_1-a_2}=Big[frac{b_1-b_2}{a_1-a_2}Big]cdot a_i+Big(frac{a_1b_2-a_2b_1}{a_1-a_2}Big), forall i>2$
Therefore, if:
There are two lines $L_i,L_j$ not parallel to each other $(a_ine a_j)$ intersecting at $(X,Y)$;
$displaystyle b_k=Big[frac{b_i-b_j}{a_i-a_j}Big]cdot a_k+Big(frac{a_ib_j-a_jb_i}{a_i-a_j}Big)=Xa_k+Y, forall kne i,j$; that is, $(X,Y)$ lies on all the remaining lines;
Then, the straight lines $L_i:= a_ix+y=b_i,iin{1,2,...,n}$ intersect at the point $displaystyle(X,Y)=Big(frac{b_i-b_j}{a_i-a_j},frac{a_ib_j-a_jb_i}{a_i-a_j}Big)$ uniquely.
answered Dec 17 '18 at 8:07
Shubham JohriShubham Johri
5,192717
$endgroup$
add a comment |
$begingroup$
The system is over-determined for $n>2$ but here is a general method. We can write the augmented matrix for the system $Abegin{bmatrix}x\yend{bmatrix}=B$ as under:
$begin{bmatrix}a_1&1&Big|&b_1\a_2&1&Big|&b_2\vdots&vdots&Big|&vdots\a_n&1&Big|&b_nend{bmatrix}$
For a unique solution to exist, we should have $2$ linearly-independent equations to solve for the $2$ unknowns. In other words, the rank of the coefficient and augmented matrices should be $2$. Recall that no more than $2$ vectors in $Bbb R^2$ can be linearly independent, so the rank of the coefficient matrix $A, text{rank}(A)le2$. For $text{rank}(A)=2$, we need to ensure at-least two $a_i$ are distinct. Say we have distinct $a_1ne0,a_2ne a_1$.
The point of intersection of $a_1x+y=b_1,a_2x+y=b_2$ is given by $(X,Y)=displaystyleBig(frac{b_1-b_2}{a_1-a_2},frac{a_1b_2-a_2b_1}{a_1-a_2}Big)$.
$displaystyle R_ito R_i-frac{a_i}{a_1}cdot R_1, i>1$
$displaystyle R_jto R_j-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdot R_2, j>2$
$simbegin{bmatrix}a_1&1&Big|&b_1\0&1-frac{a_2}{a_1}&Big|&b_2-frac{a_2}{a_1}cdot b_1\0&0&Big|&b'_3\vdots&vdots&Big|&vdots\0&0&Big|&b'_nend{bmatrix}$
$displaystyle b'_i=b_i-frac{a_i}{a_1}cdot b_1-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdotBig[b_2-frac{a_2}{a_1}cdot b_1Big] forall i>2$
For the rank of the augmented matrix to be $0$, we require $b'_i=0$
$displaystyletherefore b_i=frac{(a_i-a_2)b_1+(a_1-a_i)b_2}{a_1-a_2}=Big[frac{b_1-b_2}{a_1-a_2}Big]cdot a_i+Big(frac{a_1b_2-a_2b_1}{a_1-a_2}Big), forall i>2$
Therefore, if:
There are two lines $L_i,L_j$ not parallel to each other $(a_ine a_j)$ intersecting at $(X,Y)$;
$displaystyle b_k=Big[frac{b_i-b_j}{a_i-a_j}Big]cdot a_k+Big(frac{a_ib_j-a_jb_i}{a_i-a_j}Big)=Xa_k+Y, forall kne i,j$; that is, $(X,Y)$ lies on all the remaining lines;
Then, the straight lines $L_i:= a_ix+y=b_i,iin{1,2,...,n}$ intersect at the point $displaystyle(X,Y)=Big(frac{b_i-b_j}{a_i-a_j},frac{a_ib_j-a_jb_i}{a_i-a_j}Big)$ uniquely.
answered Dec 17 '18 at 8:07
Shubham JohriShubham Johri
5,192717
$endgroup$
The system is over-determined for $n>2$ but here is a general method. We can write the augmented matrix for the system $Abegin{bmatrix}x\yend{bmatrix}=B$ as under:
$begin{bmatrix}a_1&1&Big|&b_1\a_2&1&Big|&b_2\vdots&vdots&Big|&vdots\a_n&1&Big|&b_nend{bmatrix}$
For a unique solution to exist, we should have $2$ linearly-independent equations to solve for the $2$ unknowns. In other words, the rank of the coefficient and augmented matrices should be $2$. Recall that no more than $2$ vectors in $Bbb R^2$ can be linearly independent, so the rank of the coefficient matrix $A, text{rank}(A)le2$. For $text{rank}(A)=2$, we need to ensure at-least two $a_i$ are distinct. Say we have distinct $a_1ne0,a_2ne a_1$.
The point of intersection of $a_1x+y=b_1,a_2x+y=b_2$ is given by $(X,Y)=displaystyleBig(frac{b_1-b_2}{a_1-a_2},frac{a_1b_2-a_2b_1}{a_1-a_2}Big)$.
$displaystyle R_ito R_i-frac{a_i}{a_1}cdot R_1, i>1$
$displaystyle R_jto R_j-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdot R_2, j>2$
$simbegin{bmatrix}a_1&1&Big|&b_1\0&1-frac{a_2}{a_1}&Big|&b_2-frac{a_2}{a_1}cdot b_1\0&0&Big|&b'_3\vdots&vdots&Big|&vdots\0&0&Big|&b'_nend{bmatrix}$
$displaystyle b'_i=b_i-frac{a_i}{a_1}cdot b_1-frac{1-frac{a_i}{a_1}}{1-frac{a_2}{a_1}}cdotBig[b_2-frac{a_2}{a_1}cdot b_1Big] forall i>2$
For the rank of the augmented matrix to be $0$, we require $b'_i=0$
$displaystyletherefore b_i=frac{(a_i-a_2)b_1+(a_1-a_i)b_2}{a_1-a_2}=Big[frac{b_1-b_2}{a_1-a_2}Big]cdot a_i+Big(frac{a_1b_2-a_2b_1}{a_1-a_2}Big), forall i>2$
Therefore, if:
There are two lines $L_i,L_j$ not parallel to each other $(a_ine a_j)$ intersecting at $(X,Y)$;
$displaystyle b_k=Big[frac{b_i-b_j}{a_i-a_j}Big]cdot a_k+Big(frac{a_ib_j-a_jb_i}{a_i-a_j}Big)=Xa_k+Y, forall kne i,j$; that is, $(X,Y)$ lies on all the remaining lines;
Then, the straight lines $L_i:= a_ix+y=b_i,iin{1,2,...,n}$ intersect at the point $displaystyle(X,Y)=Big(frac{b_i-b_j}{a_i-a_j},frac{a_ib_j-a_jb_i}{a_i-a_j}Big)$ uniquely.
answered Dec 17 '18 at 8:07
Shubham JohriShubham Johri
5,192717
edited Dec 17 '18 at 13:02
answered Dec 17 '18 at 8:07
Shubham JohriShubham Johri
5,192717
answered Dec 17 '18 at 8:07
Shubham JohriShubham Johri
5,192717
answered Dec 17 '18 at 8:07
Shubham JohriShubham Johri
5,192717
5,192717
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3043601%2foverdetermined-linear-system%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Where is $b_i$ in your equation?
$endgroup$
– induction601
Dec 17 '18 at 6:35
$begingroup$
Typo! Fixed. Sorry
$endgroup$
– ersh
Dec 17 '18 at 6:42