Mixing
question asked in recent hiring [on hold]
Clash Royale CLAN TAG#URR8PPP
up vote
-4
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 yesterday
Ronald Paul
1
put on hold as off-topic by John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u yesterday
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
-4
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 yesterday
Ronald Paul
1
put on hold as off-topic by John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u yesterday
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
-4
down vote
favorite
up vote
-4
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 yesterday
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 yesterday
Ronald Paul
1
asked yesterday
Ronald Paul
1
asked yesterday
Ronald Paul
1
asked yesterday
Ronald Paul
1
1
put on hold as off-topic by John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u yesterday
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
put on hold as off-topic by John Ma, Jyrki Lahtonen, Taroccoesbrocco, TheGeekGreek, Delta-u yesterday
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
3
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 yesterday
joriki
164k10179328
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
yesterday
"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
yesterday
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
yesterday
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
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 yesterday
joriki
164k10179328
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
yesterday
"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
yesterday
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
yesterday
add a comment |Â
up vote
3
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 yesterday
joriki
164k10179328
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
yesterday
"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
yesterday
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
yesterday
add a comment |Â
up vote
3
down vote
up vote
3
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 yesterday
joriki
164k10179328
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 yesterday
joriki
164k10179328
edited yesterday
answered yesterday
joriki
164k10179328
answered yesterday
joriki
164k10179328
answered yesterday
joriki
164k10179328
164k10179328
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
yesterday
"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
yesterday
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
yesterday
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
yesterday
"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
yesterday
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
yesterday
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
yesterday
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
yesterday
"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
yesterday
"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
yesterday
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
yesterday
Thanks, you're both right -- I missed that case. I hope the edit fixes the problem?
– joriki
yesterday
add a comment |Â