How to form Matrix pairs of $m$ friends and to find common friend from all possible pairs. The Next CEO of Stack OverflowHow 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
What is the purpose of the Evocation wizard's Potent Cantrip feature?
How to transpose the 1st and -1th levels of arbitrarily nested array?
Non-deterministic sum of floats
What does convergence in distribution "in the Gromov–Hausdorff" sense mean?
How do scammers retract money, while you can’t?
What does "Its cash flow is deeply negative" mean?
Why don't programming languages automatically manage the synchronous/asynchronous problem?
What can we do to stop prior company from asking us questions?
Why am I allowed to create multiple unique pointers from a single object?
calculus parametric curve length
Novel about a guy who is possessed by the divine essence and the world ends?
How to invert MapIndexed on a ragged structure? How to construct a tree from rules?
WOW air has ceased operation, can I get my tickets refunded?
How fast would a person need to move to trick the eye?
Is it possible to search for a directory/file combination?
Should I tutor a student who I know has cheated on their homework?
What is ( CFMCC ) on ILS approach chart?
If a black hole is created from light, can this black hole then move at speed of light?
How did the Bene Gesserit know how to make a Kwisatz Haderach?
How did people program for Consoles with multiple CPUs?
Between two walls
Limits on contract work without pre-agreed price/contract (UK)
Why did we only see the N-1 starfighters in one film?
What flight has the highest ratio of time difference to flight time?
How to form Matrix pairs of $m$ friends and to find common friend from all possible pairs.
The Next CEO of Stack OverflowHow 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.
$$
beginarrayc
(i, j) & text1 & text2 & cdots \
hline
1 & 0 & 1 & cdots \
2 & 1 & 0 & cdots \
vdots & vdots & vdots \
endarray
$$
Given that $A^2(1, 2) > 0$ and $A$ gives the below matrix.
$$ left[
beginarraycc
0&1\
1&0
endarray
right] $$
And $A^2$ gives the below matrix.
$$ left[
beginarraycc
1&0\
0&1
endarray
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.
$$
beginarrayc
(i, j) & text1 & text2 & cdots \
hline
1 & 0 & 1 & cdots \
2 & 1 & 0 & cdots \
vdots & vdots & vdots \
endarray
$$
Given that $A^2(1, 2) > 0$ and $A$ gives the below matrix.
$$ left[
beginarraycc
0&1\
1&0
endarray
right] $$
And $A^2$ gives the below matrix.
$$ left[
beginarraycc
1&0\
0&1
endarray
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.
$$
beginarrayc
(i, j) & text1 & text2 & cdots \
hline
1 & 0 & 1 & cdots \
2 & 1 & 0 & cdots \
vdots & vdots & vdots \
endarray
$$
Given that $A^2(1, 2) > 0$ and $A$ gives the below matrix.
$$ left[
beginarraycc
0&1\
1&0
endarray
right] $$
And $A^2$ gives the below matrix.
$$ left[
beginarraycc
1&0\
0&1
endarray
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.
$$
beginarrayc
(i, j) & text1 & text2 & cdots \
hline
1 & 0 & 1 & cdots \
2 & 1 & 0 & cdots \
vdots & vdots & vdots \
endarray
$$
Given that $A^2(1, 2) > 0$ and $A$ gives the below matrix.
$$ left[
beginarraycc
0&1\
1&0
endarray
right] $$
And $A^2$ gives the below matrix.
$$ left[
beginarraycc
1&0\
0&1
endarray
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
1015
$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
1015
$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
1015
$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
1015
$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
1015
answered Mar 19 at 10:54
VladislavVladislav
1015
answered Mar 19 at 10:54
VladislavVladislav
1015
answered Mar 19 at 10:54
VladislavVladislav
1015
1015
$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