Symmetric 2 Dimensional Array

Question

What would the code be to test whether an array is two-dimensional? For one dimension I know that reversing the list will work. For two-dimensions I know that the opposite row / column must be the same. In other words [1][2] must equal [2][1] and so forth.

(defun symmetric-check (list) (equal list (reverse list)))

Answer 1

First of all implementing a matrix using a list of lists is inefficient if you need random access because that is going to cost O(n + m) instead of the cheaper O(1) using a bidimensional array.

To check for symmetry the first thing is ensuring that the matrix is square and then you just need to check that element m_ij is equal to element m_ji for all pairs.

Since you need checking all pairs for symmetry it makes sense to only consider i > j to avoid doing each test twice (> and not >= because clearly m_ii is equal to itself).

As an added bonus checking for symmetry doesn't require considering main diagonal elements.

(defun symmetric (m)
  (let ((rows (array-dimension m 0))
        (cols (array-dimension m 1)))
    (when (= rows cols)
      (dotimes (i rows T)
        (dotimes (j i)
          (unless (= (aref m i j) (aref m j i))
            (return-from symmetric NIL)))))))

(let ((m (make-array (list 5 5) :initial-element 0)))
  (dotimes (i 5)
    (dotimes (j 5)
      (setf (aref m i j) (* (1+ i) (1+ j)))))
  (print m)
  (print (symmetric m))
  (setf (aref m 3 2) 9)
  (print m)
  (print (symmetric m)))

Answer 2

It depends on your definition of symmetry.

In linear algebra, a matrix is called symmetric iff it is equal to its transpose (this is equivalent to saying that M[i, j] = M[j, i] for all i and j). Thus,

(defun matrix-symmetric-p (m)
  (equal m (transpose-matrix m)))

(defun transpose-matrix (m)
  ;; implement this
  ...)

I strongly recommend using actual arrays, though, because it will make doing things like this easier and much more efficient.

(defun matrix-symmetric-p (m)
  (loop for i from 0 below (array-dimension m 0)
        always
          (loop for j from 0 below (array-dimension m 1)
                always
                  (= (aref m i j) (aref m j i)))))