question asked in recent hiring [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
-6
down vote
favorite
Consider an n∗n matrix A consisting of all zeros. Find the number of ways to fill this matrix with exactly n+2 ones such that the permanent of the matrix is zero
matrices contest-math
asked Aug 5 at 4:27
Ronald Paul
1
closed as off-topic by John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u Aug 5 at 12:33
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u
add a comment |Â
up vote
-6
down vote
favorite
Consider an n∗n matrix A consisting of all zeros. Find the number of ways to fill this matrix with exactly n+2 ones such that the permanent of the matrix is zero
matrices contest-math
asked Aug 5 at 4:27
Ronald Paul
1
closed as off-topic by John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u Aug 5 at 12:33
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u
add a comment |Â
up vote
-6
down vote
favorite
up vote
-6
down vote
favorite
Consider an n∗n matrix A consisting of all zeros. Find the number of ways to fill this matrix with exactly n+2 ones such that the permanent of the matrix is zero
matrices contest-math
asked Aug 5 at 4:27
Ronald Paul
1
Consider an n∗n matrix A consisting of all zeros. Find the number of ways to fill this matrix with exactly n+2 ones such that the permanent of the matrix is zero
matrices contest-math
asked Aug 5 at 4:27
Ronald Paul
1
asked Aug 5 at 4:27
Ronald Paul
1
asked Aug 5 at 4:27
Ronald Paul
1
asked Aug 5 at 4:27
Ronald Paul
1
1
closed as off-topic by John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u Aug 5 at 12:33
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u
closed as off-topic by John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u Aug 5 at 12:33
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
There are $n!$ ways to place $n$ ones such that there is a one in every row and column, making the permanent non-zero. For each of these configurations, there are $binomn(n-1)2$ ways to add two more ones. If the two ones are placed at $i,j$ and $k,l$ and there are already ones at $i,l$ and $k,j$, then the resulting configuration is also reached by adding ones at $i,l$ and $k,j$ with the ones at $i,j$ and $k,l$ already part of the original permutation. Otherwise, there is no other way to reach the same configuration. So of the $n!binomn(n-1)2$ configurations, we have to weight $n!fracn(n-1)2$ contributions by $frac12$ because two of them correspond to the same result. Thus, the number of matrices with $n+2$ ones with non-zero permanent is $n!left(binomn(n-1)2-fracn(n-1)4right)$. The total number of matrices with $n+2$ ones is $binomn^2n+2$. Thus the number of matrices with $n+2$ ones with zero permament is
$$
binomn^2n+2-n!left(binomn(n-1)2-fracn(n-1)4right);.
$$
answered Aug 5 at 5:02
joriki
165k10180328
If I start with a $3 times 3$ identity matrix for the one in every row and column, then add ones in $(1,2)$ and $(2,1)$ I can delete $(1,1)$ and $(2,2)$ to get another matrix with a $1$ in each row and column.
– Ross Millikan
Aug 5 at 5:11
"the two ones that were added are the only two ones that can be removed while leaving a one in every row and column" -- how so? If I have a matrix with ones on the diagonal, and add a one in position $(i,j)$ and $(j,i)$, I can now remove $(i,i)$ and $(j,j)$ and still have nonzero permanent.
– Henning Makholm
Aug 5 at 5:15
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
Aug 5 at 6:43
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
There are $n!$ ways to place $n$ ones such that there is a one in every row and column, making the permanent non-zero. For each of these configurations, there are $binomn(n-1)2$ ways to add two more ones. If the two ones are placed at $i,j$ and $k,l$ and there are already ones at $i,l$ and $k,j$, then the resulting configuration is also reached by adding ones at $i,l$ and $k,j$ with the ones at $i,j$ and $k,l$ already part of the original permutation. Otherwise, there is no other way to reach the same configuration. So of the $n!binomn(n-1)2$ configurations, we have to weight $n!fracn(n-1)2$ contributions by $frac12$ because two of them correspond to the same result. Thus, the number of matrices with $n+2$ ones with non-zero permanent is $n!left(binomn(n-1)2-fracn(n-1)4right)$. The total number of matrices with $n+2$ ones is $binomn^2n+2$. Thus the number of matrices with $n+2$ ones with zero permament is
$$
binomn^2n+2-n!left(binomn(n-1)2-fracn(n-1)4right);.
$$
answered Aug 5 at 5:02
joriki
165k10180328
If I start with a $3 times 3$ identity matrix for the one in every row and column, then add ones in $(1,2)$ and $(2,1)$ I can delete $(1,1)$ and $(2,2)$ to get another matrix with a $1$ in each row and column.
– Ross Millikan
Aug 5 at 5:11
"the two ones that were added are the only two ones that can be removed while leaving a one in every row and column" -- how so? If I have a matrix with ones on the diagonal, and add a one in position $(i,j)$ and $(j,i)$, I can now remove $(i,i)$ and $(j,j)$ and still have nonzero permanent.
– Henning Makholm
Aug 5 at 5:15
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
Aug 5 at 6:43
add a comment |Â
up vote
2
down vote
There are $n!$ ways to place $n$ ones such that there is a one in every row and column, making the permanent non-zero. For each of these configurations, there are $binomn(n-1)2$ ways to add two more ones. If the two ones are placed at $i,j$ and $k,l$ and there are already ones at $i,l$ and $k,j$, then the resulting configuration is also reached by adding ones at $i,l$ and $k,j$ with the ones at $i,j$ and $k,l$ already part of the original permutation. Otherwise, there is no other way to reach the same configuration. So of the $n!binomn(n-1)2$ configurations, we have to weight $n!fracn(n-1)2$ contributions by $frac12$ because two of them correspond to the same result. Thus, the number of matrices with $n+2$ ones with non-zero permanent is $n!left(binomn(n-1)2-fracn(n-1)4right)$. The total number of matrices with $n+2$ ones is $binomn^2n+2$. Thus the number of matrices with $n+2$ ones with zero permament is
$$
binomn^2n+2-n!left(binomn(n-1)2-fracn(n-1)4right);.
$$
answered Aug 5 at 5:02
joriki
165k10180328
If I start with a $3 times 3$ identity matrix for the one in every row and column, then add ones in $(1,2)$ and $(2,1)$ I can delete $(1,1)$ and $(2,2)$ to get another matrix with a $1$ in each row and column.
– Ross Millikan
Aug 5 at 5:11
"the two ones that were added are the only two ones that can be removed while leaving a one in every row and column" -- how so? If I have a matrix with ones on the diagonal, and add a one in position $(i,j)$ and $(j,i)$, I can now remove $(i,i)$ and $(j,j)$ and still have nonzero permanent.
– Henning Makholm
Aug 5 at 5:15
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
Aug 5 at 6:43
add a comment |Â
up vote
2
down vote
up vote
2
down vote
There are $n!$ ways to place $n$ ones such that there is a one in every row and column, making the permanent non-zero. For each of these configurations, there are $binomn(n-1)2$ ways to add two more ones. If the two ones are placed at $i,j$ and $k,l$ and there are already ones at $i,l$ and $k,j$, then the resulting configuration is also reached by adding ones at $i,l$ and $k,j$ with the ones at $i,j$ and $k,l$ already part of the original permutation. Otherwise, there is no other way to reach the same configuration. So of the $n!binomn(n-1)2$ configurations, we have to weight $n!fracn(n-1)2$ contributions by $frac12$ because two of them correspond to the same result. Thus, the number of matrices with $n+2$ ones with non-zero permanent is $n!left(binomn(n-1)2-fracn(n-1)4right)$. The total number of matrices with $n+2$ ones is $binomn^2n+2$. Thus the number of matrices with $n+2$ ones with zero permament is
$$
binomn^2n+2-n!left(binomn(n-1)2-fracn(n-1)4right);.
$$
answered Aug 5 at 5:02
joriki
165k10180328
There are $n!$ ways to place $n$ ones such that there is a one in every row and column, making the permanent non-zero. For each of these configurations, there are $binomn(n-1)2$ ways to add two more ones. If the two ones are placed at $i,j$ and $k,l$ and there are already ones at $i,l$ and $k,j$, then the resulting configuration is also reached by adding ones at $i,l$ and $k,j$ with the ones at $i,j$ and $k,l$ already part of the original permutation. Otherwise, there is no other way to reach the same configuration. So of the $n!binomn(n-1)2$ configurations, we have to weight $n!fracn(n-1)2$ contributions by $frac12$ because two of them correspond to the same result. Thus, the number of matrices with $n+2$ ones with non-zero permanent is $n!left(binomn(n-1)2-fracn(n-1)4right)$. The total number of matrices with $n+2$ ones is $binomn^2n+2$. Thus the number of matrices with $n+2$ ones with zero permament is
$$
binomn^2n+2-n!left(binomn(n-1)2-fracn(n-1)4right);.
$$
answered Aug 5 at 5:02
joriki
165k10180328
edited Aug 5 at 6:41
answered Aug 5 at 5:02
joriki
165k10180328
answered Aug 5 at 5:02
joriki
165k10180328
answered Aug 5 at 5:02
joriki
165k10180328
165k10180328
If I start with a $3 times 3$ identity matrix for the one in every row and column, then add ones in $(1,2)$ and $(2,1)$ I can delete $(1,1)$ and $(2,2)$ to get another matrix with a $1$ in each row and column.
– Ross Millikan
Aug 5 at 5:11
"the two ones that were added are the only two ones that can be removed while leaving a one in every row and column" -- how so? If I have a matrix with ones on the diagonal, and add a one in position $(i,j)$ and $(j,i)$, I can now remove $(i,i)$ and $(j,j)$ and still have nonzero permanent.
– Henning Makholm
Aug 5 at 5:15
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
Aug 5 at 6:43
add a comment |Â
If I start with a $3 times 3$ identity matrix for the one in every row and column, then add ones in $(1,2)$ and $(2,1)$ I can delete $(1,1)$ and $(2,2)$ to get another matrix with a $1$ in each row and column.
– Ross Millikan
Aug 5 at 5:11
"the two ones that were added are the only two ones that can be removed while leaving a one in every row and column" -- how so? If I have a matrix with ones on the diagonal, and add a one in position $(i,j)$ and $(j,i)$, I can now remove $(i,i)$ and $(j,j)$ and still have nonzero permanent.
– Henning Makholm
Aug 5 at 5:15
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
Aug 5 at 6:43
If I start with a $3 times 3$ identity matrix for the one in every row and column, then add ones in $(1,2)$ and $(2,1)$ I can delete $(1,1)$ and $(2,2)$ to get another matrix with a $1$ in each row and column.
– Ross Millikan
Aug 5 at 5:11
If I start with a $3 times 3$ identity matrix for the one in every row and column, then add ones in $(1,2)$ and $(2,1)$ I can delete $(1,1)$ and $(2,2)$ to get another matrix with a $1$ in each row and column.
– Ross Millikan
Aug 5 at 5:11
"the two ones that were added are the only two ones that can be removed while leaving a one in every row and column" -- how so? If I have a matrix with ones on the diagonal, and add a one in position $(i,j)$ and $(j,i)$, I can now remove $(i,i)$ and $(j,j)$ and still have nonzero permanent.
– Henning Makholm
Aug 5 at 5:15
"the two ones that were added are the only two ones that can be removed while leaving a one in every row and column" -- how so? If I have a matrix with ones on the diagonal, and add a one in position $(i,j)$ and $(j,i)$, I can now remove $(i,i)$ and $(j,j)$ and still have nonzero permanent.
– Henning Makholm
Aug 5 at 5:15
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
Aug 5 at 6:43
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
Aug 5 at 6:43
add a comment |Â
