# System of equations to represent a matrix

Suppose that there is a $n \times n$ matrix. Then there will be entries $A_{ij}$ where i and j represent row and column.

Equations contain entries of a matrix, $A_{ij}$ and when the equations are solved, we will get each entry. (Add: By equations I mean like ${A_{11}}^2 + {A_{12}}^3+..$ where $A_{ij}$ would be entries of a matrix.)

Is there any way to represent the matrix using a system of only $kn$ equations where $k$ is constant for all combinations of integer entries? (Obviously, linear equations will not do this.)

Any variation of the matrix is allowed if the variation respect the following: entries ($n \times n$ of them) in the same column and row must be in the same column and row.

Edit: In linear algebra, for example, if there are $n \times n$ distinct equations, then you will be able to get entries of a matrix. This is a-bit different question.

-
What do you mean by "represent the matrix using a system of only $kn$ equations"? What is $k$? – Qiaochu Yuan Jul 10 '12 at 1:57
@QiaochuYuan constant. – Liz Calipha Jul 10 '12 at 2:01
Okay. What do you mean by representing the matrix using a system of equations? – Qiaochu Yuan Jul 10 '12 at 2:02
@QiaochuYuan Equations contain components of a matrix, $A_{ij}$ and when the equations are solved, we will get each component. And as the question says. – Liz Calipha Jul 10 '12 at 2:05
What is an $n \times n \times n$ matrix? – DonAntonio Jul 10 '12 at 2:07

This isn't really an answer, just a too long for a comment. I'll repeat myself here to make sure I understood you correctly..

Let the variables $A_{ij}, 1 \le i,j \le n$ denote the $(i,j)$th entry of the $n\times n$ matrix $A.$ Given such an $A,$ you would like to encode it as a system of polynomials: $$P_i(A_{11}, A_{12}, \ldots, A_{nn}) = 0, \quad 1 \le i \le B, \tag{1}$$ where $B$ is the total number of polynomial equations. The system $(1)$ is constructed from the entries of $A,$ and the solution to $(1)$ uniquely determines $A.$ Your question is then about how small $B$ could be? In particular, could $B = kn$ for some constant $k$?

Obviously, if $\text{deg}(P_i) = 1$ for all $i,$ i.e. a linear system, then we need $n^2$ such equations.

If $\text{deg}(P_i) = d_i > 1,$ for some (or all) $i,$ then the situation doesn't get better. Consider the situation with only 2 variables. Two lines can uniquely determine a point, because the number of intersection points is at most 1. Now consider a higher degree curve: circles ($x^2 + y^2 - c = 0$.) Two circles intersect in at most 2 points, which gives you 2 solutions, one of which is your original matrix $A,$ and the other is some other matrix similar (as far as conditions go) to your original matrix. In higher dimensions (i.e. more variables), polynomials become surfaces & intersections become curves.

In general, the number of common solutions will be proportional to the product of the degrees, by Bézout's theorem. Alas, I'm not well familiar with algebraic geometry, and other user will prove far more helpful.

Again, long comment really rather than answer.

-
Oh. That's why linear algebra is most commonly used, right? – Liz Calipha Jul 10 '12 at 4:10
What about limiting the case to integers (entries)? – Liz Calipha Jul 10 '12 at 4:10

I am not sure that I know precisely what you are looking for. However, the following may give a partial answer.

Suppose that we are working over the reals. Then the system of $m$ simultaneous equations $$P_1(x_1,\dots,x_n)=0, \quad P_2(x_1,\dots,x_n)=0,\dots\dots, \quad P_m(x_1,\dots,x_n)=0$$ is equivalent to the single equation $$\left(P_1^2(x_1,\dots,x_n)+ P_2^2(x_1,\dots,x_n)+\cdots+P_m^2(x_1,\dots,x_n)\right)=0.$$

-