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
Why do remote companies require working in the US?
Can we say or write : "No, it'sn't"?
How do we know the LHC results are robust?
multiple labels for a single equation
Would this house-rule that treats advantage as a +1 to the roll instead (and disadvantage as -1) and allows them to stack be balanced?
Are there any unintended negative consequences to allowing PCs to gain multiple levels at once in a short milestone-XP game?
Is micro rebar a better way to reinforce concrete than rebar?
How does the mv command work with external drives?
Why does the UK parliament need a vote on the political declaration?
If Nick Fury and Coulson already knew about aliens (Kree and Skrull) why did they wait until Thor's appearance to start making weapons?
What connection does MS Office have to Netscape Navigator?
What flight has the highest ratio of time difference to flight time?
Won the lottery - how do I keep the money?
Unreliable Magic - Is it worth it?
Limits on contract work without pre-agreed price/contract (UK)
Can you replace a racial trait cantrip when leveling up?
Make solar eclipses exceedingly rare, but still have new moons
Extending anchors in TikZ
Is there a difference between "Fahrstuhl" and "Aufzug"
Bold, vivid family
Why has the US not been more assertive in confronting Russia in recent years?
Is HostGator storing my password in plaintext?
Do I need to enable Dev Hub in my PROD Org?
How do I go from 300 unfinished/half written blog posts, to published posts?
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.
$$
beginarraylcr
(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[
beginarrayc
0&1\
1&0
endarray
right] $$
And $A^2$ gives the below matrix.
$$ left[
beginarrayc
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.
$$
beginarraylcr
(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[
beginarrayc
0&1\
1&0
endarray
right] $$
And $A^2$ gives the below matrix.
$$ left[
beginarrayc
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.
$$
beginarraylcr
(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[
beginarrayc
0&1\
1&0
endarray
right] $$
And $A^2$ gives the below matrix.
$$ left[
beginarrayc
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.
$$
beginarraylcr
(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[
beginarrayc
0&1\
1&0
endarray
right] $$
And $A^2$ gives the below matrix.
$$ left[
beginarrayc
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