Let $ n$ be a positive integer. Consider an $ n\times n$ matrix with entries $ 1,2,...,n^2$ written in order, starting at the top left and moving along each row in turn left-to-right. (e.g. for $ n \equal{} 3$ we get $ \left[\begin{array}{ccc}1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9\end{array}\right]$)
We choose $ n$ entries of the matrix such that exactly one entry is chosen in each row and each column. What are the possible values of the sum of the selected entries?
1. **Define the matrix \( A \)**:
   Let \( A \) be the \( n \times n \) matrix with entries \( 1, 2, \ldots, n^2 \) written in order, starting at the top left and moving along each row in turn left-to-right. For example, for \( n = 3 \), the matrix \( A \) is:
   \[
   A = \begin{bmatrix}
   1 & 2 & 3 \\
   4 & 5 & 6 \\
   7 & 8 & 9
   \end{bmatrix}
   \]

2. **Decompose the matrix \( A \)**:
   Write \( A = B + C \), where \( B \) has constant rows and \( C \) has constant columns. For instance, for \( n = 4 \):
   \[
   A = \begin{bmatrix}
   1 & 2 & 3 & 4 \\
   5 & 6 & 7 & 8 \\
   9 & 10 & 11 & 12 \\
   13 & 14 & 15 & 16
   \end{bmatrix}
   \]
   can be decomposed as:
   \[
   B = \begin{bmatrix}
   0 & 0 & 0 & 0 \\
   4 & 4 & 4 & 4 \\
   8 & 8 & 8 & 8 \\
   12 & 12 & 12 & 12
   \end{bmatrix}, \quad
   C = \begin{bmatrix}
   1 & 2 & 3 & 4 \\
   1 & 2 & 3 & 4 \\
   1 & 2 & 3 & 4 \\
   1 & 2 & 3 & 4
   \end{bmatrix}
   \]

3. **Trace of the matrix product**:
   We want to compute \( \text{trace}(PAQ) \) where \( P \) and \( Q \) are arbitrary permutation matrices. Using the linearity of the trace and the property that \( \text{trace}(UV) = \text{trace}(VU) \):
   \[
   \text{trace}(PAQ) = \text{trace}(PBQ + PCQ) = \text{trace}(PBQ) + \text{trace}(PCQ)
   \]
   Since permuting columns leaves \( B \) unchanged and permuting rows leaves \( C \) unchanged:
   \[
   \text{trace}(PBQ) = \text{trace}(BQP) = \text{trace}(B)
   \]
   \[
   \text{trace}(PCQ) = \text{trace}(QPC) = \text{trace}(C)
   \]

4. **Calculate the trace of \( B \) and \( C \)**:
   The matrix \( B \) has constant rows, and the matrix \( C \) has constant columns. The trace of \( B \) is the sum of the diagonal elements of \( B \), which are \( 0, 4, 8, \ldots, 4(n-1) \):
   \[
   \text{trace}(B) = 0 + 4 + 8 + \ldots + 4(n-1) = 4 \sum_{k=0}^{n-1} k = 4 \cdot \frac{(n-1)n}{2} = 2n(n-1)
   \]
   The trace of \( C \) is the sum of the diagonal elements of \( C \), which are \( 1, 2, 3, \ldots, n \):
   \[
   \text{trace}(C) = 1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}
   \]

5. **Sum of the traces**:
   Therefore, the trace of \( A \) is:
   \[
   \text{trace}(A) = \text{trace}(B) + \text{trace}(C) = 2n(n-1) + \frac{n(n+1)}{2}
   \]
   Simplifying this expression:
   \[
   \text{trace}(A) = 2n(n-1) + \frac{n(n+1)}{2} = 2n^2 - 2n + \frac{n^2 + n}{2} = \frac{4n^2 - 4n + n^2 + n}{2} = \frac{5n^2 - 3n}{2}
   \]

The final answer is \(\boxed{\frac{5n^2 - 3n}{2}}\).