How to form Matrix pairs of $m$ friends and to find common friend from all possible pairs.How to find the...
Are there any examples of a variable being normally distributed that is *not* due to the Central Limit Theorem?
Personal Teleportation: From Rags to Riches
Arrow those variables!
What exploit Are these user agents trying to use?
One verb to replace 'be a member of' a club
Avoiding the "not like other girls" trope?
Why can't we play rap on piano?
How does a predictive coding aid in lossless compression?
What does “the session was packed” mean in this context?
What is a romance in Latin?
Mathematica command that allows it to read my intentions
Why would the Red Woman birth a shadow if she worshipped the Lord of the Light?
Should I cover my bicycle overnight while bikepacking?
ssTTsSTtRrriinInnnnNNNIiinngg
How writing a dominant 7 sus4 chord in RNA ( Vsus7 chord in the 1st inversion)
Determining Impedance With An Antenna Analyzer
I would say: "You are another teacher", but she is a woman and I am a man
Could the museum Saturn V's be refitted for one more flight?
Examples of smooth manifolds admitting inbetween one and a continuum of complex structures
Can a virus destroy the BIOS of a modern computer?
Avoiding direct proof while writing proof by induction
Size of subfigure fitting its content (tikzpicture)
Can we compute the area of a quadrilateral with one right angle when we only know the lengths of any three sides?
Assassin's bullet with mercury
How to form Matrix pairs of $m$ friends and to find common friend from all possible pairs.
How to find the eigenvalues and Jordan canonical form of this matrixProving that an matrix have integers entriesShow a matrix M is invertible if and only if the eigenvalues of A are all distinctHow to prove or understand this linear algebra assertion?Any hint about solving this monster determinant?Creating nearest neighbors Laplacian matrixHow to find the derivative of the following matrix?How to find the inverse of the following matrix?How can I express a given matrix in a multiplication form?Help to find a factorization of a matrix into a product and sum of matrices
$begingroup$
The below is a problem given in entrance exam.
Problem:
A golf club has $m$ members with serial numbers $1, 2 . . . , m$. If members with serial numbers $i$ and $j$ are friends, then $A(i, j) = A(j, i) = 1$, otherwise $A(i, j) = A(j, i) = 0$. By convention, $A(i, i) = 0$, i.e. a person is not considered a friend of himself or herself. Let $A^k$$(i, j)$ refer to the $(i, j)$th entry in the $k^{th}$ power of the matrix $A$.
Suppose it is given that $A^9(i, j) > 0$ for all pairs $i,j$ where $1 ≤ i,j ≤ m$, $A^2$$(1,2) > 0$ and $A^4(1, 3) = 0$.
Suppose it is given that $A^9(i,j) > 0$ for all pairs $i,j$ where $1 ≤ i,j ≤ m, A^2(1,2) > 0$ and $A^4(1,3) = 0$.
Determine if below problem statements are necessarily true and please provide the reasons for it.
- Does members $1$ and $2$ have at least one friend in common.
- $m≤9$
- $m≥6$
$A^2(i,i)> 0$ for all $i$, $1≤i≤m.$
$\$
My approach:
I tried to form the question in $A(i, j)$ pairs as per the question.
$$
begin{array}{c|lcr}
(i, j) & text{1} & text{2} & cdots \
hline
1 & 0 & 1 & cdots \
2 & 1 & 0 & cdots \
vdots & vdots & vdots \
end{array}
$$
Given that $A^2(1, 2) > 0$ and $A$ gives the below matrix.
$$ left[
begin{array}{cc|c}
0&1\
1&0
end{array}
right] $$
And $A^2$ gives the below matrix.
$$ left[
begin{array}{cc|c}
1&0\
0&1
end{array}
right] $$
Determinant of this gives 1.
I could not proceed further as I am still not sure if my approach to this problem is correct or not.
Can someone please explain the approach to this problem and also let me know if there exists a book which contains these type of problems which would help me a lot.
linear-algebra matrices
asked Mar 18 at 19:13
JyoJyo
63
$endgroup$
|
show 4 more comments
$begingroup$
The below is a problem given in entrance exam.
Problem:
A golf club has $m$ members with serial numbers $1, 2 . . . , m$. If members with serial numbers $i$ and $j$ are friends, then $A(i, j) = A(j, i) = 1$, otherwise $A(i, j) = A(j, i) = 0$. By convention, $A(i, i) = 0$, i.e. a person is not considered a friend of himself or herself. Let $A^k$$(i, j)$ refer to the $(i, j)$th entry in the $k^{th}$ power of the matrix $A$.
Suppose it is given that $A^9(i, j) > 0$ for all pairs $i,j$ where $1 ≤ i,j ≤ m$, $A^2$$(1,2) > 0$ and $A^4(1, 3) = 0$.
Suppose it is given that $A^9(i,j) > 0$ for all pairs $i,j$ where $1 ≤ i,j ≤ m, A^2(1,2) > 0$ and $A^4(1,3) = 0$.
Determine if below problem statements are necessarily true and please provide the reasons for it.
- Does members $1$ and $2$ have at least one friend in common.
- $m≤9$
- $m≥6$
$A^2(i,i)> 0$ for all $i$, $1≤i≤m.$
$\$
My approach:
I tried to form the question in $A(i, j)$ pairs as per the question.
$$
begin{array}{c|lcr}
(i, j) & text{1} & text{2} & cdots \
hline
1 & 0 & 1 & cdots \
2 & 1 & 0 & cdots \
vdots & vdots & vdots \
end{array}
$$
Given that $A^2(1, 2) > 0$ and $A$ gives the below matrix.
$$ left[
begin{array}{cc|c}
0&1\
1&0
end{array}
right] $$
And $A^2$ gives the below matrix.
$$ left[
begin{array}{cc|c}
1&0\
0&1
end{array}
right] $$
Determinant of this gives 1.
I could not proceed further as I am still not sure if my approach to this problem is correct or not.
Can someone please explain the approach to this problem and also let me know if there exists a book which contains these type of problems which would help me a lot.
linear-algebra matrices
asked Mar 18 at 19:13
JyoJyo
63
$endgroup$
$begingroup$
This is my first question so please correct my mistakes if there are any.
$endgroup$
– Jyo
Mar 18 at 19:16
$begingroup$
Could you explain more clearly what the question is? I.e, what is demanded in the problem?
$endgroup$
– Matija Sreckovic
Mar 18 at 19:42
$begingroup$
@MatijaSreckovic We need to find the least 'm' value and does members 1 and 2 have at least one friend in common.
$endgroup$
– Jyo
Mar 18 at 19:45
$begingroup$
This is another one. $ A^2(i,i)>0, for all i,1≤i≤m.$
$endgroup$
– Jyo
Mar 18 at 19:47
$begingroup$
We need to tell if the given question is true or not and provide a reason for it.
$endgroup$
– Jyo
Mar 18 at 19:48
|
show 4 more comments
$begingroup$
The below is a problem given in entrance exam.
Problem:
A golf club has $m$ members with serial numbers $1, 2 . . . , m$. If members with serial numbers $i$ and $j$ are friends, then $A(i, j) = A(j, i) = 1$, otherwise $A(i, j) = A(j, i) = 0$. By convention, $A(i, i) = 0$, i.e. a person is not considered a friend of himself or herself. Let $A^k$$(i, j)$ refer to the $(i, j)$th entry in the $k^{th}$ power of the matrix $A$.
Suppose it is given that $A^9(i, j) > 0$ for all pairs $i,j$ where $1 ≤ i,j ≤ m$, $A^2$$(1,2) > 0$ and $A^4(1, 3) = 0$.
Suppose it is given that $A^9(i,j) > 0$ for all pairs $i,j$ where $1 ≤ i,j ≤ m, A^2(1,2) > 0$ and $A^4(1,3) = 0$.
Determine if below problem statements are necessarily true and please provide the reasons for it.
- Does members $1$ and $2$ have at least one friend in common.
- $m≤9$
- $m≥6$
$A^2(i,i)> 0$ for all $i$, $1≤i≤m.$
$\$
My approach:
I tried to form the question in $A(i, j)$ pairs as per the question.
$$
begin{array}{c|lcr}
(i, j) & text{1} & text{2} & cdots \
hline
1 & 0 & 1 & cdots \
2 & 1 & 0 & cdots \
vdots & vdots & vdots \
end{array}
$$
Given that $A^2(1, 2) > 0$ and $A$ gives the below matrix.
$$ left[
begin{array}{cc|c}
0&1\
1&0
end{array}
right] $$
And $A^2$ gives the below matrix.
$$ left[
begin{array}{cc|c}
1&0\
0&1
end{array}
right] $$
Determinant of this gives 1.
I could not proceed further as I am still not sure if my approach to this problem is correct or not.
Can someone please explain the approach to this problem and also let me know if there exists a book which contains these type of problems which would help me a lot.
linear-algebra matrices
asked Mar 18 at 19:13
JyoJyo
63
$endgroup$
The below is a problem given in entrance exam.
Problem:
A golf club has $m$ members with serial numbers $1, 2 . . . , m$. If members with serial numbers $i$ and $j$ are friends, then $A(i, j) = A(j, i) = 1$, otherwise $A(i, j) = A(j, i) = 0$. By convention, $A(i, i) = 0$, i.e. a person is not considered a friend of himself or herself. Let $A^k$$(i, j)$ refer to the $(i, j)$th entry in the $k^{th}$ power of the matrix $A$.
Suppose it is given that $A^9(i, j) > 0$ for all pairs $i,j$ where $1 ≤ i,j ≤ m$, $A^2$$(1,2) > 0$ and $A^4(1, 3) = 0$.
Suppose it is given that $A^9(i,j) > 0$ for all pairs $i,j$ where $1 ≤ i,j ≤ m, A^2(1,2) > 0$ and $A^4(1,3) = 0$.
Determine if below problem statements are necessarily true and please provide the reasons for it.
- Does members $1$ and $2$ have at least one friend in common.
- $m≤9$
- $m≥6$
$A^2(i,i)> 0$ for all $i$, $1≤i≤m.$
$\$
My approach:
I tried to form the question in $A(i, j)$ pairs as per the question.
$$
begin{array}{c|lcr}
(i, j) & text{1} & text{2} & cdots \
hline
1 & 0 & 1 & cdots \
2 & 1 & 0 & cdots \
vdots & vdots & vdots \
end{array}
$$
Given that $A^2(1, 2) > 0$ and $A$ gives the below matrix.
$$ left[
begin{array}{cc|c}
0&1\
1&0
end{array}
right] $$
And $A^2$ gives the below matrix.
$$ left[
begin{array}{cc|c}
1&0\
0&1
end{array}
right] $$
Determinant of this gives 1.
I could not proceed further as I am still not sure if my approach to this problem is correct or not.
Can someone please explain the approach to this problem and also let me know if there exists a book which contains these type of problems which would help me a lot.
linear-algebra matrices
linear-algebra matrices
asked Mar 18 at 19:13
JyoJyo
63
asked Mar 18 at 19:13
JyoJyo
63
edited Mar 19 at 6:44
Jyo
asked Mar 18 at 19:13
JyoJyo
63
asked Mar 18 at 19:13
JyoJyo
63
asked Mar 18 at 19:13
JyoJyo
63
63
$begingroup$
This is my first question so please correct my mistakes if there are any.
$endgroup$
– Jyo
Mar 18 at 19:16
$begingroup$
Could you explain more clearly what the question is? I.e, what is demanded in the problem?
$endgroup$
– Matija Sreckovic
Mar 18 at 19:42
$begingroup$
@MatijaSreckovic We need to find the least 'm' value and does members 1 and 2 have at least one friend in common.
$endgroup$
– Jyo
Mar 18 at 19:45
$begingroup$
This is another one. $ A^2(i,i)>0, for all i,1≤i≤m.$
$endgroup$
– Jyo
Mar 18 at 19:47
$begingroup$
We need to tell if the given question is true or not and provide a reason for it.
$endgroup$
– Jyo
Mar 18 at 19:48
|
show 4 more comments
$begingroup$
This is my first question so please correct my mistakes if there are any.
$endgroup$
– Jyo
Mar 18 at 19:16
$begingroup$
Could you explain more clearly what the question is? I.e, what is demanded in the problem?
$endgroup$
– Matija Sreckovic
Mar 18 at 19:42
$begingroup$
@MatijaSreckovic We need to find the least 'm' value and does members 1 and 2 have at least one friend in common.
$endgroup$
– Jyo
Mar 18 at 19:45
$begingroup$
This is another one. $ A^2(i,i)>0, for all i,1≤i≤m.$
$endgroup$
– Jyo
Mar 18 at 19:47
$begingroup$
We need to tell if the given question is true or not and provide a reason for it.
$endgroup$
– Jyo
Mar 18 at 19:48
$begingroup$
This is my first question so please correct my mistakes if there are any.
$endgroup$
– Jyo
Mar 18 at 19:16
$begingroup$
This is my first question so please correct my mistakes if there are any.
$endgroup$
– Jyo
Mar 18 at 19:16
$begingroup$
Could you explain more clearly what the question is? I.e, what is demanded in the problem?
$endgroup$
– Matija Sreckovic
Mar 18 at 19:42
$begingroup$
Could you explain more clearly what the question is? I.e, what is demanded in the problem?
$endgroup$
– Matija Sreckovic
Mar 18 at 19:42
$begingroup$
@MatijaSreckovic We need to find the least 'm' value and does members 1 and 2 have at least one friend in common.
$endgroup$
– Jyo
Mar 18 at 19:45
$begingroup$
@MatijaSreckovic We need to find the least 'm' value and does members 1 and 2 have at least one friend in common.
$endgroup$
– Jyo
Mar 18 at 19:45
$begingroup$
This is another one. $ A^2(i,i)>0, for all i,1≤i≤m.$
$endgroup$
– Jyo
Mar 18 at 19:47
$begingroup$
This is another one. $ A^2(i,i)>0, for all i,1≤i≤m.$
$endgroup$
– Jyo
Mar 18 at 19:47
$begingroup$
We need to tell if the given question is true or not and provide a reason for it.
$endgroup$
– Jyo
Mar 18 at 19:48
$begingroup$
We need to tell if the given question is true or not and provide a reason for it.
$endgroup$
– Jyo
Mar 18 at 19:48
|
show 4 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Not a complete solution, but some thoughts.
The well-known fact (you can easily prove it by induction) is that $k$th power of adjacency matrix $A$ is a matrix of pathes that have length $k$. Thus, $A^{k}(i, j)$ equals to number of pathes from $i$ to $j$ that have length $k$. In this terms, $A^9(i, j) > 0$ means there is a path from $i$ to $j$ of length 9, $A^2(1, 2) > 0$ means there is a path from $1$ to $2$ of length 2, and $A^4(1, 3) = 0$ means there is no path from $1$ to $3$ of length 4. Now, this
members $1$ and $2$ have at least one friend in common.
immediatly follows from $A^2(1, 2) > 0$ as you have a path $1 to x to2$ and $x$ is a common friend for $1$ and $2$.
answered Mar 19 at 10:54
VladislavVladislav
1165
$endgroup$
$begingroup$
Thanks a lot. I have no idea about Graph Theory. Now I will learn.
$endgroup$
– Jyo
Mar 20 at 15:16
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%2f3153192%2fhow-to-form-matrix-pairs-of-m-friends-and-to-find-common-friend-from-all-possi%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$
Not a complete solution, but some thoughts.
The well-known fact (you can easily prove it by induction) is that $k$th power of adjacency matrix $A$ is a matrix of pathes that have length $k$. Thus, $A^{k}(i, j)$ equals to number of pathes from $i$ to $j$ that have length $k$. In this terms, $A^9(i, j) > 0$ means there is a path from $i$ to $j$ of length 9, $A^2(1, 2) > 0$ means there is a path from $1$ to $2$ of length 2, and $A^4(1, 3) = 0$ means there is no path from $1$ to $3$ of length 4. Now, this
members $1$ and $2$ have at least one friend in common.
immediatly follows from $A^2(1, 2) > 0$ as you have a path $1 to x to2$ and $x$ is a common friend for $1$ and $2$.
answered Mar 19 at 10:54
VladislavVladislav
1165
$endgroup$
$begingroup$
Thanks a lot. I have no idea about Graph Theory. Now I will learn.
$endgroup$
– Jyo
Mar 20 at 15:16
add a comment |
$begingroup$
Not a complete solution, but some thoughts.
The well-known fact (you can easily prove it by induction) is that $k$th power of adjacency matrix $A$ is a matrix of pathes that have length $k$. Thus, $A^{k}(i, j)$ equals to number of pathes from $i$ to $j$ that have length $k$. In this terms, $A^9(i, j) > 0$ means there is a path from $i$ to $j$ of length 9, $A^2(1, 2) > 0$ means there is a path from $1$ to $2$ of length 2, and $A^4(1, 3) = 0$ means there is no path from $1$ to $3$ of length 4. Now, this
members $1$ and $2$ have at least one friend in common.
immediatly follows from $A^2(1, 2) > 0$ as you have a path $1 to x to2$ and $x$ is a common friend for $1$ and $2$.
answered Mar 19 at 10:54
VladislavVladislav
1165
$endgroup$
$begingroup$
Thanks a lot. I have no idea about Graph Theory. Now I will learn.
$endgroup$
– Jyo
Mar 20 at 15:16
add a comment |
$begingroup$
Not a complete solution, but some thoughts.
The well-known fact (you can easily prove it by induction) is that $k$th power of adjacency matrix $A$ is a matrix of pathes that have length $k$. Thus, $A^{k}(i, j)$ equals to number of pathes from $i$ to $j$ that have length $k$. In this terms, $A^9(i, j) > 0$ means there is a path from $i$ to $j$ of length 9, $A^2(1, 2) > 0$ means there is a path from $1$ to $2$ of length 2, and $A^4(1, 3) = 0$ means there is no path from $1$ to $3$ of length 4. Now, this
members $1$ and $2$ have at least one friend in common.
immediatly follows from $A^2(1, 2) > 0$ as you have a path $1 to x to2$ and $x$ is a common friend for $1$ and $2$.
answered Mar 19 at 10:54
VladislavVladislav
1165
$endgroup$
Not a complete solution, but some thoughts.
The well-known fact (you can easily prove it by induction) is that $k$th power of adjacency matrix $A$ is a matrix of pathes that have length $k$. Thus, $A^{k}(i, j)$ equals to number of pathes from $i$ to $j$ that have length $k$. In this terms, $A^9(i, j) > 0$ means there is a path from $i$ to $j$ of length 9, $A^2(1, 2) > 0$ means there is a path from $1$ to $2$ of length 2, and $A^4(1, 3) = 0$ means there is no path from $1$ to $3$ of length 4. Now, this
members $1$ and $2$ have at least one friend in common.
immediatly follows from $A^2(1, 2) > 0$ as you have a path $1 to x to2$ and $x$ is a common friend for $1$ and $2$.
answered Mar 19 at 10:54
VladislavVladislav
1165
answered Mar 19 at 10:54
VladislavVladislav
1165
answered Mar 19 at 10:54
VladislavVladislav
1165
answered Mar 19 at 10:54
VladislavVladislav
1165
1165
$begingroup$
Thanks a lot. I have no idea about Graph Theory. Now I will learn.
$endgroup$
– Jyo
Mar 20 at 15:16
add a comment |
$begingroup$
Thanks a lot. I have no idea about Graph Theory. Now I will learn.
$endgroup$
– Jyo
Mar 20 at 15:16
$begingroup$
Thanks a lot. I have no idea about Graph Theory. Now I will learn.
$endgroup$
– Jyo
Mar 20 at 15:16
$begingroup$
Thanks a lot. I have no idea about Graph Theory. Now I will learn.
$endgroup$
– Jyo
Mar 20 at 15:16
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%2f3153192%2fhow-to-form-matrix-pairs-of-m-friends-and-to-find-common-friend-from-all-possi%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$
This is my first question so please correct my mistakes if there are any.
$endgroup$
– Jyo
Mar 18 at 19:16
$begingroup$
Could you explain more clearly what the question is? I.e, what is demanded in the problem?
$endgroup$
– Matija Sreckovic
Mar 18 at 19:42
$begingroup$
@MatijaSreckovic We need to find the least 'm' value and does members 1 and 2 have at least one friend in common.
$endgroup$
– Jyo
Mar 18 at 19:45
$begingroup$
This is another one. $ A^2(i,i)>0, for all i,1≤i≤m.$
$endgroup$
– Jyo
Mar 18 at 19:47
$begingroup$
We need to tell if the given question is true or not and provide a reason for it.
$endgroup$
– Jyo
Mar 18 at 19:48