Question: Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix?  Someone comes along and gives us the partition $P=\{2,2,3,3,4\}$ of $14$.  How can we determine if there's a $5 \times 5$ matrix whose rows and column sums both give rise to that partition?  In the example, it's realized by this matrix: $$\begin{bmatrix} 1 &amp; 0 &amp; 1 &amp; 1 &amp; 0 \\ 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; 1 &amp; 0 &amp; 1 &amp;  1 \\ 1 &amp; 0 &amp; 1 &amp; 1 &amp; 1 \\ 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\ \end{bmatrix}$$ but I cheated: I generated the example partition from the matrix.    Observations:   The obvious necessary condition is that $\max P \leq |P|$. This is equivalent to asking when is $P$ the out-degree sequence of a directed graph where any vertex may have one loop.  (So the  or  could be applied in some cases, replacing each undirected edge with a bidirected edge; in fact, they would work in my above example.) If we just brute force started filling in $1$'s, we can get stuck.  Here I proceed row-by-row, placing a $1$ wherever possible: $$ \begin{array}{c|ccccc}   &amp; 4 &amp; 3 &amp; 3 &amp; 2 &amp; 2 \\ \hline 4 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 0 \\ 3 &amp; 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 \\ 3 &amp; 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 \\ 2 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\ 2 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; ??? \\ \end{array} $$     Motivation:  This is a first step in an attempt at answering my Mathoverflow question: .  An answer to this question might help reduce the search space.
123656
We are given ($a_1,a_2,....,a_m$) and ($b_1, b_2,....,b_n$) sequences with non-negative integers.   Decide whether it's possible and if it is construct a matrix $\Re^{m x n}$ of ones("1") and zeros("0") where the number of ones("1") in row $i$ is $\forall i $ : $a_i$ and in column $j$ is $\forall j$ : $b_j$   Any hint is greatly appreciated.
32566
I read this formula in some book but it didn't provide a proof so I thought someone on this website could figure it out. What it says is: If we consider 3 non-concurrent, non parallel lines represented by the equations : $$a_1x+b_1y+c_1=0$$ $$a_2x+b_2y+c_2=0$$ $$a_3x+b_3y+c_3=0$$ Then the area of the triangle that these lines will enclose is given by the magnitude of : $$\frac{det\begin{bmatrix}a_1 &amp; b_1 &amp; c_1\\a_2 &amp; b_2 &amp; c_2\\a_3 &amp; b_3 &amp; c_3\end{bmatrix}^2}{2C_1C_2C_3}$$ Where $C_1,C_2,C_3$ are the co-factors of $c_1,c_2,c_3$ respectively in the above matrix.  What I'm wondering is, where did this come from? And why isn't it famous? Earlier we had to calculate areas by finding the vertices and all but this does it in a minute or so and thus deserves more familiarity.
110248
I am working through the proof for partitioning sum of squares. Could someone please explicitly explain how one goes from line 14 to 15 in the following PDF:     That is, how one moves between these lines -   \begin{align} \rm{SSTO} &amp;= \sum_{i=1}^r \sum_{j=1}^{n_i} (Y_{ij}-\overline{Y}_{..})^2 \\ &amp;= \sum_{i=1}^r \sum_{j=1}^{n_i} [(Y_{ij}-\overline{Y}_{i.})+(\overline{Y}_{i.}-\overline{Y}_{..})]^2 \end{align}  I'm actually reading through Casella and Berger's "Statistical Inference" (pg 536), but the same jump occurs in both.  Sorry, I was never the best at algebra... would someone please explain this.
5536
If we let $S_n$ denote the symmetric group on $n$ letters, then any element in $S_n$ can be written as the product of disjoint cycles, and for $k$ disjoint cycles, $\sigma_1,\sigma_2,\ldots,\sigma_k$, we have that $|\sigma_1\sigma_2\ldots\sigma_k|=\operatorname{lcm}(\sigma_1,\sigma_2,\ldots,\sigma_k)$.  So to find the maximum order of an element in $S_n$, we need to maximize $\operatorname{lcm}(\sigma_1,\sigma_2,\ldots,\sigma_k)$ given that $\sum_{i=1}^k{|\sigma_i|}=n$. So my question:      How can we determine $|\sigma_1|,|\sigma_2|,\ldots,|\sigma_k|$ such that $\sum_{i=1}^k{|\sigma_i|}=n$ and $\operatorname{lcm}(\sigma_1,\sigma_2,\ldots,\sigma_k)$ is at a maximum?   Example  For $S_{10}$ we have that the maximal order of an element consists of 3 cycles of length 2,3, and 5 (or so I think) resulting in an element order of $\operatorname{lcm}(2,3,5)=30$.  I'm certain that the all of the magnitudes will have to be relatively prime to achieve the greatest lcm, but other than this, I don't know how to proceed. Any thoughts or references? Thanks so much.
117923
Let $G = (V, E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup  ... \cup V_n$ be a partition of its $4n$ vertices into n pairwise disjoint subsets, each of cardinality 4. Is it true that there must be an independent set of $G$ containing precisely one vertex from each $V_i$? (Prove or supply a counter example.)  I think this is not right because just consider square with four vertices and four edges,but I have doubt that it is proper counter example.please help with your knowledge,thank you very much.    actually this is exercise 4 of chapter 5 from alon spencer probabilistic method.so I also tag this question as mentioned.
84597
Let $A \in \mathbb{F}^{m \times n}$. How do you prove that row rank of a matrix equals column rank ?  This question has been addressed  and , but the explanation in one case was descriptive and somewhat involved in the other. The answer below is an introductory-linear-algebra level answer.
17573
It seems to me like the answer should be $n!$. Since you can first select the first vertex, then select each remaining vertex until you've got them all in a permutation.  My textbook, however, says that the answer is $(1/2)(n-1)!$  Unfortunately, it doesn't explain why this is. Why is it?
73327
Show that any number of partitions of $2r + k$ into $r + k$ parts is the same for any $k$.   I've tried this, but I haven't come up with anything; hence why I have nothing written here. But in any case, any sort of help is appreciated.
43169
How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be:        f(n) = 4f(n-1) - 2f(n-2)   where f(0) = 1     and f(1) = 1    but the recurrence relation only counts the cases in which at least one side (either top, bottom, left or right of the original rectangle) is not split into sub-rectangles. There are many other partitions that don't belong to those simple cases like  [EDIT ImageShack has removed the picture. One of the cases is the sixth partition when n = 4 in the picture in the accepted answer below.]  Any other related problem suggestions are welcome. Also it is nice to know how to traverse this partition efficiently.
114424
I have read that if $A$ is the adjacency matrix of a tree $T$, then we have that  $$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k} $$  where $N_k(T)$ is the number of matchings of size $k$ of $T$.  However, I couldn't find a proof. Does anyone know how to do it? Thanks!
114526
Let $n$ be a positive integer. Show that the matrix  $$\begin{pmatrix} 1 &amp; 1/2 &amp; 1/3 &amp; \cdots &amp; 1/n \\ 1/2 &amp; 1/3 &amp; 1/4 &amp; \cdots &amp; 1/(n+1) \\ \vdots &amp; \vdots &amp;  \vdots &amp; \ddots &amp; \vdots\\ 1/n &amp; 1/(n+1) &amp; 1/(n+2) &amp; \cdots &amp; 1/(2n-1) \end{pmatrix}$$  is invertible and all the entries of its inverse are integers. This is an exercise in Hoffman and Kunze's linear algebra book. Any hints will be appreciated!
113877
Need help with this proof using Ferrers' graph or otherwise.    Show that the number of partitions of $r+k$ into $k$ parts is equal to     The number of partitions of $r + {k+1 \choose 2}$ into $ k $ distinct parts   The number of partitions of $r$ into parts of size at most $k$
95790
A friend was in need of an algorithm that would let him loop through the elements of an NxM matrix (N and M are odd). I came up with a solution, but I wanted to see if my fellow SO'ers could come up with a better solution.  I'm posting my solution as an answer to this question.  Example Output:  For a 3x3 matrix, the output should be:  (0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)    Furthermore, the algorithm should support non-square matrices, so for example for a 5x3 matrix, the output should be:  (0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)
26561
I know that the partition of $2n$ items into $n$ pairs has something to do with double factorial, but I am not sure how many possibilities we exactly have.   We can choose such a partition into pairs by first choosing $n$ elements to be in one half and the remaining $n$ in the other half, which gives ${{2n} \choose n}$ possibilities. Then we can take a permutation of both sets and match them accordingly.   This gives $${{2n} \choose n} n! n!=\frac{(2n)! n! n!}{n! n!}=(2n)!$$ possibilities. But with this we overcount, since we do not want the pairs to be ordered. Each of the $n$ pairs is counted twice, wherefore we have to divide by 2 for every pair, hence $\frac{(2n)!}{2^n}$?   Well, another possiblity to do that is just to iteratively pick $2$ elements among the remaining ones, which gives ${{2n} \choose 2} {{2n-2} \choose 2} \dotsb {4 \choose 2}$  I am not sure, but I do not think that this is the same and also, I do not see the connection to double factorial. Would be very glad if you could help me with these 3 possiblities.   Thank you.
15141
I need to find $|GL_2(F_p)|$, I am very very uncomfortable in counting, so please help here I proceed,  $\begin{pmatrix}a&amp;b\\c&amp;d\end{pmatrix}$ be such an invertible matrix, so we need and sufficient that $ad\neq bc$, so if i chose all non zero $a,b,c$ arbitrarily and chose $d\neq a^{-1}bc$ and form matrices then the cardinality   will be $(q-1)^3\times (q-2)$, well now if one of $a,b,c,d$ be zero then other three can be anything nonzero so in this case cardinality will be $4(q-1)^3$, so finally if two entries are $0$ then they must be opposite to each other i.e diagonally, but other two must be nonzero, so cardinality in that case $2(q-1)^2$, so total number is just sum of three cases.
31652
Problem:  If a set $A$ has $n$ elements in it, how many reflexive relations can be defined on it?  My solution  Is the answer  summation of (n^2 - n)C(i)  for i=0 to n^2 -n  $$\sum_{i=0}^{n^2-n} C(n^2-n,i) = \sum_{i=0}^{n^2-n} \binom{n^2-n}i$$  How? well if i make a matrix $n\times n$  now the diagonal elements have to be selected,out of remaining $n^2-n$ any number of elements can be selected.
34183
I want to find the rank of this $n\times n$ matrix \begin{pmatrix} 1 &amp; a &amp; a &amp; \cdots &amp; \cdots &amp; a \\ a &amp; 1 &amp; a &amp; \cdots &amp; \cdots &amp; a \\ a &amp; a &amp; 1 &amp; a &amp; \cdots &amp; a \\ \vdots &amp; \vdots &amp; a&amp; \ddots &amp; &amp; \vdots\\ \vdots &amp; \vdots &amp; \vdots &amp; &amp; \ddots &amp; \vdots \\ a &amp; a &amp; a &amp; \cdots  &amp;\cdots &amp; 1 \end{pmatrix}  that is, the matrix whose diagonals are $1's$ and $a$ otherwise, where $a$ is any real number.  My first observation is when $a=0$ the rank is $n$ and when $a=1$ the rank is $1.$ Then I can assume $a\neq 0, 1$ and proceed row reduction to find its pivot rows. I obtain  \begin{pmatrix} 1 &amp; a &amp; a &amp; \cdots  &amp; a \\ 0 &amp; 1+a &amp; a &amp; \cdots &amp; a \\ 0 &amp; a &amp; 1+a &amp; \cdots &amp; a \\ \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ 0 &amp; a &amp; a &amp; \cdots  &amp; 1+a \end{pmatrix} by subtracting the first row multiplied $a$ for each row below the first, and then divides the factor $(1-a)$,  and stuck there. Any hints/helps?